python - 折叠树中到尖端的平均距离 < x 的子树

Question

我有一个 Newick 格式的层次树，例如:

(A:0.556705,(B:0.251059,C:0.251059):0.305646):0.556705;

括号代表树拓扑(进化枝结构/分组)，数字代表分支长度(距离)，例如:

我需要折叠到尖端(终端节点/尖端/叶子)的平均距离小于给定值 x 的分支(子树)。这样输入和折叠的输出都是 Newick 格式。例如，如果 x 为 0.29，则上面的 B 和 C 折叠为 BC，我们得到如下内容:

(A:0.556705,BC:0.556705):0.556705;

是否有一种简单的方法可以在给定任何 Newick 树(例如在 Python 中)的情况下以编程方式实现这种折叠？

Answer 1

这个快速且脏代码片段似乎适用于您的最小树，但我需要更多示例数据来使用更复杂的树检查它:

#! /usr/bin/python3

class Tree:
    def __init__ (self, tokens):
        self.children = []
        while tokens:
            self.children.append ( (tokens [1], float (tokens [0] ) ) )
            tokens = tokens [2:]

    def __repr__ (self):
        return '<{}>'.format (self.children)

    def pprint (self, indent = 0):
        prefix = '  ' * indent
        for child, dist in self.children:
            if isinstance (child, Tree):
                print (prefix, dist)
                child.pprint (indent + 1)
            else:
                print (prefix, child, dist)

    def collapse (self, limit):
        self.children = [ (child.collapse (limit) [0], dist)
            if isinstance (child, Tree)
            else (child, dist) for child, dist in self.children]
        avg = sum (dist for _, dist in self.children) / len (self.children)
        if avg > limit:
            return (self, 0)
        else:
            if any (isinstance (child, Tree) for child in self.children):
                print ('Would like to collapse, but cannot, as at least one child is a tree.')
                return (self, 0)
            return (''.join (child for child, _ in self.children), 0)


def parse (tree):
    stack = []
    buff = ''
    while True:
        c = tree [0]
        if c == ';': break
        tree = tree [1:]
        if c == '(':
            stack.insert (0, '(')
            continue
        if c == ')':
            if buff: stack.insert (0, buff)
            buff = ''
            popped = ''
            tokens = []
            while True:
                token = stack [0]
                stack = stack [1:]
                if token == '(': break
                tokens.append (token)
            stack.insert (0, Tree (tokens) )
            continue
        if c in ':,':
            if buff: stack.insert (0, buff)
            buff = ''
            continue
        buff += c
    if buff: stack.insert (0, buff)
    return Tree (stack)

t = parse ('(A:0.556705,(B:0.251059,C:0.251059):0.305646):0.556705;')
t.pprint ()
t.collapse (.3)
print ()
t.pprint ()

未折叠的树是:

 0.556705
   0.305646
     C 0.251059
     B 0.251059
   A 0.556705

0.3 折叠的树是:

 0.556705
   CB 0.305646
   A 0.556705

1.0 折叠的树是:

CBA 0.556705

折叠0.1的树是:

 0.556705
   0.305646
     C 0.251059
     B 0.251059
   A 0.556705

<小时/>

这里是代码的另一个更清晰的版本(它产生 nerwick 表示法输出):

NOTA BENE:输入树必须加括号。

#! /usr/bin/python3

class Tree:
    def __init__ (self, weight, children):
        self.weight = weight
        self.children = children [:]

    def distances (self, curDistance = .0, acc = None):
        if acc is None: acc = []
        for child in self.children:
            child.distances (self.weight + curDistance, acc)
        return acc

    def collapse (self, limit):
        self.children = [child.collapse (limit) for child in self.children]
        distances = self.distances (-self.weight)
        avg = sum (distances) / len (distances)
        if avg > limit: return self
        return Node (self.weight, ''.join (self.descendants () ) )

    def descendants (self):
        descendants = []
        for child in self.children:
            descendants.extend (child.descendants () )
        return descendants

    def __repr__ (self):
        return '({}):{}'.format (','.join (str (child) for child in self.children), self.weight)

class Node:
    def __init__ (self, weight, name):
        self.weight = weight
        self.name = name

    def distances (self, curDistance, acc):
        acc.append (curDistance + self.weight)

    def collapse (self, limit):
        return self

    def descendants (self):
        return [self.name]

    def __repr__ (self):
        return '{}:{}'.format (self.name, self.weight)

class Stack (list):
    def pop (self):
        e = self [0]
        del self [0]
        return e

    def push (self, e):
        self.insert (0, e)

def parse (tree):
    buff = ''
    stack = Stack ()
    while True:
        c = tree [0]
        if c == ';': break
        tree = tree [1:]

        if c == '(':
            stack.push (c)
            continue

        if c in ':,':
            if buff: stack.push (buff)
            buff = ''
            continue

        if c == ')':
            if buff: stack.push (buff)
            buff = ''
            popped = ''
            children = []
            while True:
                weight = stack.pop ()
                if weight == '(': break
                weight = float (weight)
                child = stack.pop ()
                if isinstance (child, Tree):
                    child.weight = weight
                else:
                    child = Node (weight, child)
                children.append (child)
            stack.push (Tree (0, children) )
            continue

        buff += c

    return stack.pop ()

t = parse ('((A:0.9,(B:0.2,C:0.3):0.3,(E:0.05,F:0.08):0.1):0.6);')
print ('Input tree is {}'.format (t) )
for limit in range (1, 6):
    limit = limit / 10
    print ('Collapsed by {} is {}'.format (limit, t.collapse (limit) ) )

输出是(修改输入):

Input tree is (((F:0.08,E:0.05):0.1,(C:0.3,B:0.2):0.3,A:0.9):0.6):0
Collapsed by 0.1 is ((FE:0.1,(C:0.3,B:0.2):0.3,A:0.9):0.6):0
Collapsed by 0.2 is ((FE:0.1,(C:0.3,B:0.2):0.3,A:0.9):0.6):0
Collapsed by 0.3 is ((FE:0.1,CB:0.3,A:0.9):0.6):0
Collapsed by 0.4 is ((FE:0.1,CB:0.3,A:0.9):0.6):0
Collapsed by 0.5 is (FECBA:0.6):0