Computing Phylogenetic Roots with Bounded Degrees and Errors Open Access
Descriptions
 Author or creator

Jiang, Tao
Chen, ZhiZhong
Lin, Guohui
 Additional contributors

 Subject/Keyword

phylogenic root
computational biology
NPhard
efficient algorithm
Phylogeny
 Type of item
 Computing Science Technical Report
 Computing science technical report ID

TR0306
 Language

English
 Place
 Time
 Description

Technical report TR0306. Given a set of species and their similarity data, an important problem in evolutionary biology is how to reconstruct a phylogeny (also called evolutionary tree) so that species are close in the phylogeny if and only if they have high similarity. Assume that the similarity data are represented as a graph G = (V, E) where each vertex represents a species and two vertices are adjacent if they represent species of high similarity. The phylogeny reconstruction problem can then be abstracted as the problem of finding a (phylogenetic) tree T from the given graph G such that (1) T has no degree2 internal nodes, (2) the external nodes (i.e. leaves) of T are exactly the elements of V, and (3) (u, v) ε E if and only if d_T(u, v) ≤ k for some fixed threshold k, where d_T(u,v) denotes the distance between u and v in tree T. This is called the Phylogenetic kth Root Problem (PRk), and such a tree T, if exists, is called a phylogenetic kth root of graph G. The computational complexity of PRk is open, except for k ≤ 4. In this paper, we investigate PRk under a natural restriction that the maximum degree of the phylogenetic root is bounded from above by a constant. Our main contribution is a lineartime algorithm that determines if G has such a phylogenetic kth root, and if so, demonstrates one. On the other hand, as in practice the collected similarity data are usually not perfect and may contain errors, we propose to study a generalized version of PRk where the output phylogeny is only required to be an approximate root of the input graph. We show that this and other related problems are computationally intractable.
 Date created

2003
 DOI

doi:10.7939/R3W17X
 License information
 Creative Commons Attribution 3.0 Unported
 Rights
 Citation for previous publication

 Source
 Link to related item

File Details
 Date Uploaded
 20120605T16:00:13.000Z
 Date Modified
 20140429T16:46:15.860+00:00
 Audit Status
 Audits have not yet been run on this file.
 Characterization

File format: pdf (Portable Document Format)
Mime type: application/pdf
File size: 290245
Last modified: 2015:10:12 13:03:5406:00
Filename: TR0306.pdf
Original checksum: 779c2a9933dd758daf78d5637085100e
Well formed: true
Valid: true
File title: Introduction
Page count: 21
Activity of users you follow
User Activity 
Date 