Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Saved Items

Supertrees by Flipping

D. ChenContact Information, O. EulensteinContact Information, David Fernández-BacaContact Information and M. SandersonContact Information

(6)  Department of Computer Science, Iowa State University, Ames, IA 50011, USA
(7)  Section of Evolution and Ecology, University of California, Davis, CA 95616, USA
Abstract
The input to a supertree problem is a collection of phyloge-netic trees that intersect pairwise in their leaf sets; the goal is to construct a single tree that retains as much as possible of the information in the input. This task is complicated by inconsistencies due to errors. We consider the case where the source trees are rooted and are represented by the clusters they exhibit. The problem is to find the minimum number of flips needed to resolve all inconsistencies, where each flip moves a taxon into or out of a cluster. We prove that the minimum flip problem is $$
\mathcal{N}\mathcal{P}
$$ -complete, but show that it is fixed-parameter tractable and give an approximation algorithm for a special case.
Research of D. Chen, O. Eulenstein, and M. Sanderson supported in part by the National Science Foundation (NSF) under grant no. 0075319. D. Fernández-Baca was supported in part by NSF under grant CCR-9520946.

Contact Information D. Chen
Email: jackie@cs.iastate.edu

Contact Information O. Eulenstein
Email: oeulenst@cs.iastate.edu

Contact Information David Fernández-Baca
Email: fernande@cs.iastate.edu

Contact Information M. Sanderson
Email: mjsanderson@ucdavis.edu
Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.



Export this chapter
Export this chapter as RIS | Text
 
Referenced by
1 newer article

  1. Snir, Sagi (2006) . IEEE/ACM Transactions on Computational Biology and Bioinformatics 3(4)
    [CrossRef]
Remote Address: 38.107.191.109 • Server: MPWEB25
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)