This decommissioned ERA site remains active temporarily to support our final migration steps to https://ualberta.scholaris.ca, ERA's new home. All new collections and items, including Spring 2025 theses, are at that site. For assistance, please contact erahelp@ualberta.ca.
- 399 views
- 365 downloads
5th Phylogenetic Root Construction for Strictly Chordal Graphs
-
- Author(s) / Creator(s)
-
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
-
- Type of Item
- Report
-
- License
- Attribution 3.0 International