5th Phylogenetic Root Construction for Strictly Chordal Graphs

• Author(s) / Creator(s)

  • Lin, Guohui
  • Kennedy, William

• Technical report TR05-18. 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 of the tree, corresponding to the organisms, are within a specified distance of k in the tree if connected in the relationship graph. This problem, the kth phylogenetic root construction, has known linear time algorithms for k <= 4. However, the computational complexity is unknown if k >= 5. We present a polynomial time algorithm for strictly chordal relationship graphs if k = 5. | TRID-ID TR05-18

• Date created

  2005

• Subjects / Keywords

  • Phylogenetic root
  • Chordal
  • Phylogeny reconstruction
  • Strictly chordal
  • Computational biology
  • Steiner root

• Type of Item

  Report

• DOI

  https://doi.org/10.7939/R3FF3M00Z

• License

  Attribution 3.0 International