Paper Info
Title
Phylogenetic Reconstruction Algorithms Based on Weighted 4-Trees
Abstract
Quartet methods first compute 4-taxon trees (or 4-trees) then use a combinatorial algorithm to infer a phylogeny that closely respects the inferred 4-trees. This article focuses on the special case involving weighted 4-trees. The sum of the weights of the 4-trees induced by the inferred phylogeny is a natural measurement of the fit between this phylogeny and the 4-tree set. In order to measure the fit of each edge of the inferred tree, we propose a new criterion that takes the weights of the 4-trees along with the way they are grouped into account. However, finding the tree that optimizes the natural criterion is NP-hard [10], and optimizing our new criterion is likely not easier. We then describe two greedy heuristic algorithms that are experimentally efficient in optimizing these criteria and have an O(n4) time complexity (where n is the number of studied taxa). We use computer simulations to show that these two algorithms have better topological accuracy than QUARTET PUZZLING [12], which is one of the few quartet methods able to take 4-trees weighting into account, and seems to be widely used.
Year
DOI
Venue
2000
10.1007/3-540-45727-5_8
JOBIM
Keywords
Field
DocType
phylogenetic reconstruction,4-trees weighting,weighted 4-trees,natural measurement,4-tree set,new criterion,quartet puzzling,combinatorial algorithm,4-taxon tree,quartet method,natural criterion,computer simulation,time complexity,greedy heuristic
Weighting,Combinatorial algorithms,Phylogenetic reconstruction,Algorithm,Greedy algorithm,Time complexity,Mathematics,Special case
Conference
ISBN
Citations 
PageRank 
3-540-42242-0
0
0.34
References 
Authors
3
2
Name
Order
Citations
PageRank
Vincent Ranwez131020.35
Olivier Gascuel243376.01