Abstract
In this paper we propose a new method for reconstructing phylogenetic networks under the assumption that recombination events have occurred rarely. For a fixed number of recombinations, we give a generalization of the maximum parsimony criterion. Furthermore, we describe an exact algorithm for one recombination event and show that in this case our method is not only able to identify the recombined sequence but also to reliably reconstruct the complete evolutionary history.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Althaus, E., Naujoks, R.: Computing steiner minimum trees in hamming metric. In: Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 172–181 (2006)
Chare, E., Gould, E., Holmes, E.: Phylogenetic analysis reveals a low rate of homologous recombination in negative-sense rna viruses. J. Gen. Virol. 84 (2003)
Fitch, W.M.: Toward defining the course of evolution: minimum change for a specified tree topology. Systematic Zoology 20 (1971)
Gusfield, D., Eddhu, S., Langley, C.: Efficient reconstruction of phylogenetic networks with constrained recombination. In: Proceedings of the IEEE Computer Society Conference on Bioinformatics (2003)
Hein, J.: A heuristic method to reconstruct the history of sequences subject to recombination. J. Mol. Evol. 36 (1993)
Huson, D.H., Kloepper, T.H.: Computing recombination networks from binary sequences. Bioinformatics 21(2), 159–165 (2005)
Jin, G., Nakhleh, L., Snir, S., Tuller, T.: Inferring phylogenetic networks by the maximum parsimony criterion: A case study. Molecular Biology and Evolution 24(1) (2005)
Jin, G., Nakhleh, L., Snir, S., Tuller, T.: Efficient parsimony-based methods for phylogenetic network reconstruction. Bioinformatics 23(2) (2007)
Kececioglu, J., Gusfield, D.: Reconstructing a history of recombinations from a set of sequences. Discrete Appl. Math. 88(1-3), 239–260 (1998)
Makarenkov, V., Kevorkov, D., Legendre, P.: Phylogenetic network reconstruction approaches. Bioinformatics 6 (2006)
Maydt, J., Lengauer, T.: Recco: recombination analysis using cost optimization. Bioinformatics 22(9), 1064–1071 (2006)
Morin, M.M., Moret, B.M.E.: Netgen: generating phylogenetic networks with diploid hybrids. Bioinformatics 22(15) (2006)
Nakhleh, L., Jin, G., Zhao, F., Mellor-Crummey, J.: Reconstructing phylogenetic networks using maximum parsimony. In: Proceedings of the 2005 IEEE Computational Systems Bioinformatics Conference, Stanford (2005)
Polzin, T.: Algorithms for the Steiner Problem in Networks. PhD thesis, Universität des Saarlandes (2003)
Posada, D., Crandall, K.A., Holmes, E.C.: Recombination in evolutionary genomics. Annu. Rev. Genet. 36 (2002)
Rambaut, A., Grassly, N.C.: Seq-gen: an application for the monte carlo simulation of dna sequence evolution along phylogenetic trees. Computer Applications in the Biosciences 13(3), 235–238 (1997)
Ruths, D., Nakhleh, L.: Recombination and phylogeny: Effects and detection. International Journal on Bioinformatics Research and Applications 1(2) (2005)
Wang, L., Zhang, K., Zhang, L.: Perfect phylogenetic networks with recombination. Journal of Computational Biology 8 (2001)
http://www.bioinf.manchester.ac.uk/recombination/programs.shtml
http://evolution.genetics.washington.edu/phylip/software.html#Recombinant
http://evolution.genetics.washington.edu/phylip/software.html
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Althaus, E., Naujoks, R. (2008). Reconstructing Phylogenetic Networks with One Recombination. In: McGeoch, C.C. (eds) Experimental Algorithms. WEA 2008. Lecture Notes in Computer Science, vol 5038. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-68552-4_21
Download citation
DOI: https://doi.org/10.1007/978-3-540-68552-4_21
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-68548-7
Online ISBN: 978-3-540-68552-4
eBook Packages: Computer ScienceComputer Science (R0)