The Library
Inferring evolutionary trees with strong combinatorial evidence
Tools
Berry, Vincent and Gascuel, Olivier (2000) Inferring evolutionary trees with strong combinatorial evidence. Theoretical Computer Science, Volume 240 (Number 2). pp. 271-298. ISSN 0304-3975.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1016/S0304-3975(99)00235-2
Abstract
We consider the problem of inferring the evolutionary tree of a set of n species. We propose a quartet reconstruction method which specifically produces trees whose edges have strong combinatorial evidence. Let Q be a set of resolved quartets defined on the studied species, the method computes the unique maximum subset Q* of Q which is equivalent to a tree and outputs the corresponding tree as an estimate of the species' phylogeny. We use a characterization of the subset Q* due to Bandelt and Dress (Adv. Appl. Math. 7 (1986) 309-343) to provide an O(n(4)) incremental algorithm for this variant of the NP-hard quartet consistency problem. Moreover, when chosing the resolution of the quartets by the four-Point method (FPM) and considering the Cavender-Farris model of evolution, we show that the convergence rate of the Q* method is at worst polynomial when the maximum evolutive distance between two species is bounded. We complete these theoretical results by an experimental study on real and simulated data sets. The results show that (i) as expected, the strong combinatorial constraints it imposes on each edge leads the Q* method to propose very few incorrect edges; (ii) more surprisingly; the method infers trees with a relatively high degree of resolution.
Item Type: | Journal Article | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
Journal or Publication Title: | Theoretical Computer Science | ||||
Publisher: | Elsevier Science BV | ||||
ISSN: | 0304-3975 | ||||
Official Date: | 17 June 2000 | ||||
Dates: |
|
||||
Volume: | Volume 240 | ||||
Number: | Number 2 | ||||
Number of Pages: | 28 | ||||
Page Range: | pp. 271-298 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access | ||||
Title of Event: | 3rd Annual International Computing and Combinatorics Conference (COCOON 97) | ||||
Location of Event: | Shanghai, China | ||||
Date(s) of Event: | 20-22 Aug 1997 |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |