Advertisement
Published in:
2005 | OriginalPaper | Chapter
5-th Phylogenetic Root Construction for Strictly Chordal Graphs
Authors : William Kennedy, Guohui Lin
Published in: Algorithms and Computation
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Reconstruction of an evolutionary history for a set of organisms is an important research subject in computational biology. One approach motivated by graph theory constructs a relationship graph based on pairwise evolutionary closeness. The approach builds a tree representation equivalent to this graph such that leaves, corresponding to the organisms, are within a specified distance of
k
in the tree if connected in the relationship graph. This problem, the
k
-th phylogenetic root construction, has known linear time algorithms for
k
≤ 4. However, the computational complexity is unknown when
k
≥ 5. We present a polynomial time algorithm for strictly chordal relationship graphs when
k
= 5.