python中嵌套树字典的common_ancestor函数

Question

我正在尝试创建一个名为"common_ancestor()“的函数，该函数接受两个输入:第一个输入是字符串分类名列表，第二个输入是系统发育树字典。它应该返回一个字符串，该字符串给出了输入列表中所有物种的最接近共同祖先的分类单元的名称。我已经创建了一个名为"list_ancestors“的单独函数，它为我提供了列表中元素的一般祖先。另外，还有一本我正在用的字典。

    tax_dict = { 
'Pan troglodytes': 'Hominoidea',       'Pongo abelii': 'Hominoidea', 
'Hominoidea': 'Simiiformes',           'Simiiformes': 'Haplorrhini', 
'Tarsius tarsier': 'Tarsiiformes',     'Haplorrhini': 'Primates',
'Tarsiiformes': 'Haplorrhini',         'Loris tardigradus':'Lorisidae',
'Lorisidae': 'Strepsirrhini',          'Strepsirrhini': 'Primates',
'Allocebus trichotis': 'Lemuriformes', 'Lemuriformes': 'Strepsirrhini',
'Galago alleni': 'Lorisiformes',       'Lorisiformes': 'Strepsirrhini',
'Galago moholi': 'Lorisiformes'
} 

def halfroot(tree):
    taxon = random.choice(list(tree))
    result = [taxon]
    for i in range(0,len(tree)): 
        result.append(tree.get(taxon))
        taxon = tree.get(taxon)
    return result


def root(tree):
    rootlist = halfroot(tree)
    rootlist2 = rootlist[::-1]
    newlist = []
    for e in range(0,len(rootlist)):
        if rootlist2[e] != None:
        newlist.append(rootlist2[e])
    return newlist[0]


def list_ancestors(taxon, tree):
    result = [taxon]
    while taxon != root(tree):
        result.append(tree.get(taxon))
        taxon = tree.get(taxon)
    return result

def common_ancestors(inputlist,tree)
    biglist1 = []
    for i in range(0,len(listname)):
        biglist1.append(list_ancestors(listname[i],tree))
        "continue so that I get three separate lists where i can cross reference all elements from the first list to every other list to find a common ancestor "

结果应该如下所示

  print(common_ancestor([’Hominoidea’, ’Pan troglodytes’,’Lorisiformes’], tax_dict)
  Output: ’Primates’"

Answer 1

一种方法是收集每个物种的所有祖先，将它们放在一个集合中，然后进行交集，以获得它们的共同点：

def common_ancestor(species_list, tree):
    result = None  # initiate a `None` result
    for species in species_list:  # loop through each species in the species_list
        ancestors = {species}  # initiate the ancestors set with the species itself
        while True:  # rinse & repeat until there are leaves in the ancestral tree
            try:
                species = tree[species]  # get the species' ancestor
                ancestors.add(species)  # store it in the ancestors set
            except KeyError:
                break
        # initiate the result or intersect it with ancestors from the previous species
        result = ancestors if result is None else result & ancestors
    # finally, return the ancestor if there is only one in the result, or None
    return result.pop() if result and len(result) == 1 else None

print(common_ancestor(["Hominoidea", "Pan troglodytes", "Lorisiformes"], tax_dict))
# Primates

您也可以将此函数的“中间”部分用于list_ancestors() -没有必要通过尝试查找树的根来使其复杂化：

def list_ancestors(species, tree, include_self=True):
    ancestors = [species] if include_self else []
    while True:
        try:
            species = tree[species]
            ancestors.append(species)
        except KeyError:
            break
    return ancestors

当然，两者都依赖于有效的祖先树字典-如果一些祖先在自己身上递归，或者如果链中有一个断裂，它就不会工作。另外，如果你要做很多这样的操作，把你的平面字典变成一个合适的树可能是值得的。