Построение phylogentic дерева

Question

У меня есть список из списка списков, как этот

matches = [[['rootrank', 'Root'], ['domain', 'Bacteria'], ['phylum', 'Firmicutes'], ['class', 'Clostridia'], ['order', 'Clostridiales'], ['family', 'Lachnospiraceae'], ['genus', 'Lachnospira']], 
      [['rootrank', 'Root'], ['domain', 'Bacteria'], ['phylum', '"Proteobacteria"'], ['class', 'Gammaproteobacteria'], ['order', '"Vibrionales"'], ['family', 'Vibrionaceae'], ['genus', 'Catenococcus']], 
      [['rootrank', 'Root'], ['domain', 'Archaea'], ['phylum', '"Euryarchaeota"'], ['class', '"Methanomicrobia"'], ['order', 'Methanomicrobiales'], ['family', 'Methanomicrobiaceae'], ['genus', 'Methanoplanus']]] 

И я хочу, чтобы построить филогенетическое дерево из них. Я написал класс узла, как так (на основе частично на this code):

class Node(object): 
    """Generic n-ary tree node object 
    Children are additive; no provision for deleting them.""" 

    def __init__(self, parent, category=None, name=None): 
     self.parent = parent 
     self.category = category 
     self.name = name 
     self.childList = [] 

     if parent is None: 
      self.birthOrder = 0 
     else: 
      self.birthOrder = len(parent.childList) 
      parent.childList.append(self) 

    def fullPath(self): 
     """Returns a list of children from root to self""" 
     result = [] 
     parent = self.parent 
     kid  = self 

     while parent: 
      result.insert(0, kid) 
      parent, kid = parent.parent, parent 

     return result 

    def ID(self): 
     return '{0}|{1}'.format(self.category, self.name) 

И тогда я пытаюсь построить свое дерево, как это:

node = None 
for match in matches: 
    for branch in match: 
     category, name = branch 
     node = Node(node, category, name) 
     print [n.ID() for n in node.fullPath()] 

Это работает для первого матча, но когда я начинаю со вторым совпадением оно добавляется в конце дерева, а не начинается снова вверху. Как мне это сделать? Я пробовал некоторые варианты поиска ID, но я не могу заставить его работать.

Answer 1

Проблема заключается в том, что node всегда является самым узким узлом в дереве, и вы всегда добавляете этот узел. Вам нужно сохранить корневой узел. Поскольку ['rootrank', 'Root'] появляется в начале каждого из списков, я бы рекомендовал вытащить это и использовать его в качестве корня. Таким образом, вы можете сделать что-то вроде:

rootnode = Node(None, 'rootrank', 'Root') 
for match in matches: 
    node = rootnode 
    for branch in match: 
     category, name = branch 
     node = Node(node, category, name) 
     print [n.ID() for n in node.fullPath()] 

Это сделает matches список более удобным для чтения, и дает ожидаемый результат.

Answer 2

Сделайте себе одолжение и не изобретайте велосипед. Python-graph (a.k.a. pygraph) делает все, что вы просите здесь, и большинство вещей, которые вы зададите дальше.

Answer 3

Я очень рекомендую использовать библиотеку филогенетики, такую ​​как Dendropy.

«Стандартный способ написания филогенетических деревьев имеет формат Newick (в скобках, например ((A, B), C)). Если вы используете Dendropy, читая это дерево было бы так просто, как

>>> import dendropy 
>>> tree1 = dendropy.Tree.get_from_string("((A,B),(C,D))", schema="newick") 

или читать из потока

>>> tree1 = dendropy.Tree(stream=open("mle.tre"), schema="newick") 

Создатель библиотеки поддерживает хороший tutorial тоже.