sábado, 30 de abril de 2011

What is CoPhylogeny?

The cophylogeny reconstruction problem Is NP-complete


Department of Computer Science, Harvey Mudd College, 301 Platt Boulevard, Claremont, CA 91711, United States


Abstract

The cophylogeny reconstruction problem is that of finding minimum cost explanations of differences between historical associations. The problem arises in parisitology, molecular systematics, and biogeography. Existing software tools for this problem either have worst-case exponential time or use heuristics that do not guarantee optimal solutions. To date, no polynomial time optimal algorithms have been found for this problem. In this article, we prove that the problem is NP-complete, suggesting that future research on algorithms for this problem should seek better polynomial-time approximation algorithms and heuristics rather than optimal solutions. © Copyright 2011, Mary Ann Liebert, Inc.

Language of original document

English

Author keywords

coevolution; computational complexity; cophylogeny; NP-completeness

References (9) View in table layout


Charleston, M.A.

Jungles: A new solution to the host/parasite phylogeny reconciliation problem
(1998) Mathematical Biosciences, 149 (2), pp. 191-223. Cited 91 times.
doi: 10.1016/S0025-5564(97)10012-8

Charleston, M.

Principles of cophylogeny maps
(2002) Biological Evolution and Statistical Physics. Cited 2 times.
In Lässig, M., Valleriani, A., eds. Springer-Verlag, New York.

  • Locate full-text (Opens in a new window)
Conow, C., Fielder, D., Ovadia, Y., Libeskind-Hadas, R.

Jane: A new tool for the cophylogeny reconstruction problem
(2010) Algorithms for Molecular Biology, 5 (1), art. no. 16. Cited 4 times.
http://www.almob.org/content/5/1/16
doi: 10.1186/1748-7188-5-16

Garey, M., Johnson, D.
(1979) Computers and Intractability: A Guide to the Theory of NP-Completeness. Cited 12355 times.
W.H. Freeman and Company, New York.

  • Locate full-text (Opens in a new window)
Libeskind-Hadas, R., Charleston, M.A.

On the computational complexity of the reticulate cophylogeny reconstruction problem
(2009) Journal of Computational Biology, 16 (1), pp. 105-117. Cited 6 times.
doi: 10.1089/cmb.2008.0084

Merkle, D., Middendorf, M.

Reconstruction of the cophylogenetic history of related phylogenetic trees with divergence timing information
(2005) Theory in Biosciences, 123 (4), pp. 277-299. Cited 7 times.
doi: 10.1016/j.thbio.2005.01.003

Page, R.D.M.

Parallel Phylogenies: Reconstructing the History of Host-Parasite Assemblages
(1994) Cladistics, 10 (2), pp. 155-173. Cited 177 times.
doi: 10.1006/clad.1994.1010

Ronquist, F.

Three-dimensional cost-matrix optimization and maximum cospeciation
(1998) Cladistics, 14 (2), pp. 167-172. Cited 24 times.
doi: 10.1006/clad.1998.0066

Stevens, J.

Computational aspects of host-parasite phylogenies.
(2004) Briefings in bioinformatics, 5 (4), pp. 339-349. Cited 14 times.

Correspondence address Libeskind-Hadas, R.; Department of Computer Science, Harvey Mudd College, 301 Platt Boulevard, Claremont, CA 91711, United States; email:hadas@cs.hmc.edu
© Copyright 2011 Elsevier B.V., All rights reserved.

Journal of Computational Biology
Volume 18, Issue 1, 1 January 2011, Pages 59-65

No hay comentarios:

Publicar un comentario en la entrada

ciencia global al cuadrado...