TY - JOUR
T1 - Finding maximal leaf-agreement isomorphic descendent subtrees from phylogenetic trees with different species
AU - Hsieh, Sun Yuan
PY - 2007/2/12
Y1 - 2007/2/12
N2 - Phylogenetic trees are an important tool to help in the understanding of relationships between objects that evolve through time, in particular molecular sequences. In this paper, we consider two descendent subtree-comparison problems on phylogenetic trees. Given a set of k phylogenetic trees whose leaves are drawn from {1, 2, ..., n} and the leaves for two arbitrary trees are not necessary the same, we first present a linear-time algorithm to final all the maximal leaf-agreement descendent subtrees. Based on this result, we also present a linear-time algorithm to find all the maximal leaf-agreement isomorphic descendent subtrees.
AB - Phylogenetic trees are an important tool to help in the understanding of relationships between objects that evolve through time, in particular molecular sequences. In this paper, we consider two descendent subtree-comparison problems on phylogenetic trees. Given a set of k phylogenetic trees whose leaves are drawn from {1, 2, ..., n} and the leaves for two arbitrary trees are not necessary the same, we first present a linear-time algorithm to final all the maximal leaf-agreement descendent subtrees. Based on this result, we also present a linear-time algorithm to find all the maximal leaf-agreement isomorphic descendent subtrees.
UR - http://www.scopus.com/inward/record.url?scp=33846215446&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=33846215446&partnerID=8YFLogxK
U2 - 10.1016/j.tcs.2006.10.028
DO - 10.1016/j.tcs.2006.10.028
M3 - Article
AN - SCOPUS:33846215446
SN - 0304-3975
VL - 370
SP - 299
EP - 308
JO - Theoretical Computer Science
JF - Theoretical Computer Science
IS - 1-3
ER -