Nothing Special   »   [go: up one dir, main page]

Skip to main content

Reconstructing Phylogenetic Networks with One Recombination

  • Conference paper
Experimental Algorithms (WEA 2008)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 5038))

Included in the following conference series:

  • 2328 Accesses

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.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. 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)

    Google Scholar 

  2. 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)

    Google Scholar 

  3. Fitch, W.M.: Toward defining the course of evolution: minimum change for a specified tree topology. Systematic Zoology 20 (1971)

    Google Scholar 

  4. 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)

    Google Scholar 

  5. Hein, J.: A heuristic method to reconstruct the history of sequences subject to recombination. J. Mol. Evol. 36 (1993)

    Google Scholar 

  6. Huson, D.H., Kloepper, T.H.: Computing recombination networks from binary sequences. Bioinformatics 21(2), 159–165 (2005)

    Article  Google Scholar 

  7. 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)

    Google Scholar 

  8. Jin, G., Nakhleh, L., Snir, S., Tuller, T.: Efficient parsimony-based methods for phylogenetic network reconstruction. Bioinformatics 23(2) (2007)

    Google Scholar 

  9. Kececioglu, J., Gusfield, D.: Reconstructing a history of recombinations from a set of sequences. Discrete Appl. Math. 88(1-3), 239–260 (1998)

    Article  MATH  MathSciNet  Google Scholar 

  10. Makarenkov, V., Kevorkov, D., Legendre, P.: Phylogenetic network reconstruction approaches. Bioinformatics 6 (2006)

    Google Scholar 

  11. Maydt, J., Lengauer, T.: Recco: recombination analysis using cost optimization. Bioinformatics 22(9), 1064–1071 (2006)

    Article  Google Scholar 

  12. Morin, M.M., Moret, B.M.E.: Netgen: generating phylogenetic networks with diploid hybrids. Bioinformatics 22(15) (2006)

    Google Scholar 

  13. 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)

    Google Scholar 

  14. Polzin, T.: Algorithms for the Steiner Problem in Networks. PhD thesis, Universität des Saarlandes (2003)

    Google Scholar 

  15. Posada, D., Crandall, K.A., Holmes, E.C.: Recombination in evolutionary genomics. Annu. Rev. Genet. 36 (2002)

    Google Scholar 

  16. 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)

    Google Scholar 

  17. Ruths, D., Nakhleh, L.: Recombination and phylogeny: Effects and detection. International Journal on Bioinformatics Research and Applications 1(2) (2005)

    Google Scholar 

  18. Wang, L., Zhang, K., Zhang, L.: Perfect phylogenetic networks with recombination. Journal of Computational Biology 8 (2001)

    Google Scholar 

  19. http://www.bioinf.manchester.ac.uk/recombination/programs.shtml

  20. http://evolution.genetics.washington.edu/phylip/software.html#Recombinant

  21. http://evolution.genetics.washington.edu/phylip/software.html

Download references

Author information

Authors and Affiliations

Authors

Editor information

Catherine C. McGeoch

Rights and permissions

Reprints 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)

Publish with us

Policies and ethics