This is a decommissioned version of ERA which is running to enable completion of migration processes. All new collections and items and all edits to existing items should go to our new ERA instance at https://ualberta.scholaris.ca - Please contact us at erahelp@ualberta.ca for assistance!
- 383 views
- 344 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