Document Open Access Logo

Making Sense of a Cophylogeny Output: Efficient Listing of Representative Reconciliations

Authors Yishu Wang, Arnaud Mary, Marie-France Sagot, Blerina Sinaimeri

PDF
Thumbnail PDF

File

LIPIcs.WABI.2021.3.pdf
  • Filesize: 0.85 MB
  • 18 pages

Document Identifiers

Author Details

Yishu Wang
  • Université de Lyon, Université Lyon 1, CNRS, Laboratoire de Biométrie et Biologie Evolutive UMR 5558, F-69622 Villeurbanne, France
  • Inria Grenoble Rhône-Alpes, Villeurbanne, France
Arnaud Mary
  • Université de Lyon, Université Lyon 1, CNRS, Laboratoire de Biométrie et Biologie Evolutive UMR 5558, F-69622 Villeurbanne, France
  • Inria Grenoble Rhône-Alpes, Villeurbanne, France
Marie-France Sagot
  • Inria Grenoble Rhône-Alpes, Villeurbanne, France
  • Université de Lyon, Université Lyon 1, CNRS, Laboratoire de Biométrie et Biologie Evolutive UMR 5558, F-69622 Villeurbanne, France
Blerina Sinaimeri
  • Luiss University, Rome, Italy
  • ERABLE team, Inria Grenoble Rhône-Alpes, Villeurbanne, France

Cite As Get BibTex

Yishu Wang, Arnaud Mary, Marie-France Sagot, and Blerina Sinaimeri. Making Sense of a Cophylogeny Output: Efficient Listing of Representative Reconciliations. In 21st International Workshop on Algorithms in Bioinformatics (WABI 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 201, pp. 3:1-3:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.WABI.2021.3

Abstract

Cophylogeny reconciliation is a powerful method for analyzing host-parasite (or host-symbiont) co-evolution. It models co-evolution as an optimization problem where the set of all optimal solutions may represent different biological scenarios which thus need to be analyzed separately. Despite the significant research done in the area, few approaches have addressed the problem of helping the biologist deal with the often huge space of optimal solutions. In this paper, we propose a new approach to tackle this problem. We introduce three different criteria under which two solutions may be considered biologically equivalent, and then we propose polynomial-delay algorithms that enumerate only one representative per equivalence class (without listing all the solutions). Our results are of both theoretical and practical importance. Indeed, as shown by the experiments, we are able to significantly reduce the space of optimal solutions while still maintaining important biological information about the whole space.

Subject Classification

ACM Subject Classification
  • Theory of computation → Dynamic programming
  • Mathematics of computing → Graph enumeration
  • Theory of computation → Backtracking
Keywords
  • Cophylogeny
  • Enumeration
  • Equivalence relation
  • Dynamic programming

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Steen A. Andersson, David Madigan, and Michael D. Perlman. A characterization of markov equivalence classes for acyclic digraphs. Annals of Statistics, 25(2):505-541, April 1997. Google Scholar
  2. Mukul S. Bansal, Eric J. Alm, and Manolis Kellis. Reconciliation revisited: handling multiple optima when reconciling with duplication, transfer, and loss. Journal of computational biology : a journal of computational molecular cell biology, 20(10):738-754, October 2013. URL: https://doi.org/10.1089/cmb.2013.0073.
  3. Anselm Blumer, Janet A. Blumer, David H. Haussler, Ross M. McConnell, and Andrzej Ehrenfeucht. Complete inverted files for efficient text retrieval and analysis. Journal of the ACM, 34(3):578–595, July 1987. URL: https://doi.org/10.1145/28869.28873.
  4. Marília D.V. Braga, Marie-France Sagot, Céline Scornavacca, and Eric Tannier. Exploring the solution space of sorting by reversals, with experiments and an application to evolution. IEEE/ACM transactions on computational biology and bioinformatics, 5(3):348-356, 2008. URL: https://doi.org/10.1109/TCBB.2008.16.
  5. Michael A. Charleston. Jungles: a new solution to the host/parasite phylogeny reconciliation problem. Mathematical biosciences, 149:191-223, 1998. URL: https://doi.org/10.1016/s0025-5564(97)10012-8.
  6. Michael A. Charleston. Recent results in cophylogeny mapping. Advances in Parasitology, 54:303-330, December 2003. URL: https://doi.org/10.1016/s0065-308x(03)54007-6.
  7. Beatrice Donati, Christian Baudet, Blerina Sinaimeri, Pierluigi Crescenzi, and Marie-France Sagot. Eucalypt: efficient tree reconciliation enumerator. Algorithms for Molecular Biology, 10(1):3, 2015. URL: https://doi.org/10.1186/s13015-014-0031-3.
  8. Graham J. Etherington, Susan M. Ring, Michael A. Charleston, Jo Dicks, Vic J. Rayward-Smith, and Ian N. Roberts. Tracing the origin and co-phylogeny of the caliciviruses. Journal of General Virology, 87(5):1229-1235, 2006. URL: https://doi.org/10.1099/vir.0.81635-0.
  9. Robert Giegerich, Björn Voß, and Marc Rehmsmeier. Abstract shapes of RNA. Nucleic Acids Research, 32(16):4843-4851, January 2004. URL: https://doi.org/10.1093/nar/gkh779.
  10. Morris Goodman, John Czelusniak, G. William Moore, A. E. Romero-Herrera, and Genji Matsuda. Fitting the gene lineage into its species lineage, a parsimony strategy illustrated by cladograms constructed from globin sequences. Systematic Zoology, 28(2):132-163, 1979. URL: https://doi.org/10.2307/2412519.
  11. Melissa Grueter, Kalani Duran, Ramya Ramalingam, and Ran Libeskind-Hadas. Reconciliation reconsidered: In search of a most representative reconciliation in the duplication-transfer-loss model. IEEE/ACM Transactions on Computational Biology and Bioinformatics, pages 1-1, 2019. URL: https://doi.org/10.1109/TCBB.2019.2942015.
  12. Jordan Haack, Eli Zupke, Andrew Ramirez, Yi-Chieh Wu, and Ran Libeskind-Hadas. Computing the diameter of the space of maximum parsimony reconciliations in the duplication-transfer-loss model. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 16(1):14-22, 2019. URL: https://doi.org/10.1109/TCBB.2018.2849732.
  13. Katharina T Huber, Vincent Moulton, Marie-France Sagot, and Blerina Sinaimeri. Exploring and Visualizing Spaces of Tree Reconciliations. Systematic Biology, 68(4):607-618, December 2018. URL: https://doi.org/10.1093/sysbio/syy075.
  14. Katharina T. Huber, Vincent Moulton, Marie-France Sagot, and Blerina Sinaimeri. Geometric medians in reconciliation spaces of phylogenetic trees. Information Processing Letters, 136:96-101, 2018. URL: https://doi.org/10.1016/j.ipl.2018.04.001.
  15. Edwin Jacox, Cedric Chauve, Gergely J. Szöllősi, Yann Ponty, and Celine Scornavacca. ecceTERA: Comprehensive gene tree-species tree reconciliation using parsimony. Bioinformatics, 2016. URL: https://doi.org/10.1093/bioinformatics/btw105.
  16. Bonnie R. Lei and Kevin J. Olival. Contrasting patterns in mammal–bacteria coevolution: Bartonella and leptospira in bats and rodents. PLOS Neglected Tropical Diseases, 8(3):1-11, March 2014. URL: https://doi.org/10.1371/journal.pntd.0002738.
  17. Weiyun Ma, Dmitriy Smirnov, Juliet Forman, Annalise Schweickart, Carter Slocum, Srinidhi Srinivasan, and Ran Libeskind-Hadas. Dtl-rnb: Algorithms and tools for summarizing the space of dtl reconciliations. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 15(2):411-421, 2018. URL: https://doi.org/10.1109/TCBB.2016.2537319.
  18. Ross Mawhorter and Ran Libeskind-Hadas. Hierarchical clustering of maximum parsimony reconciliations. BMC Bioinformatics, 20:612, 2019. URL: https://doi.org/10.1186/s12859-019-3223-5.
  19. Daniel Merkle and Martin Middendorf. Reconstruction of the cophylogenetic history of related phylogenetic trees with divergence timing information. Theory in Biosciences, 123:277-299, 2005. URL: https://doi.org/10.1016/j.thbio.2005.01.003.
  20. Daniel Merkle, Martin Middendorf, and Nicolas Wieseke. A parameter-adaptive dynamic programming approach for inferring cophylogenies. BMC Bioinformatics, 11(Supplementary 1):10 pages, January 2010. URL: https://doi.org/10.1186/1471-2105-11-S1-S60.
  21. Kazuyuki Narisawa, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda. Efficient computation of substring equivalence classes with suffix arrays. In Bin Ma and Kaizhong Zhang, editors, Combinatorial Pattern Matching, pages 340-351, Berlin, Heidelberg, 2007. Springer Berlin Heidelberg. URL: https://doi.org/10.1007/s00453-016-0178-z.
  22. Thi-Hau Nguyen, Vincent Ranwez, Vincent Berry, and Celine Scornavacca. Support measures to estimate the reliability of evolutionary events predicted by reconciliation methods. PLOS ONE, 8(10):1-14, 2013. URL: https://doi.org/10.1371/journal.pone.0073667.
  23. Nils J. Nilsson. Principles of Artificial Intelligence. Springer-Verlag Berlin Heidelberg, Tioga, Palo Alto, CA, 1982. Google Scholar
  24. Alex Ozdemir, Michael Sheely, Daniel Bork, Ricson Cheng, Reyna Hulett, Jean Sung, Jincheng Wang, and Ran Libeskind-Hadas. Clustering the space of maximum parsimony reconciliations in the duplication-transfer-loss model. In Algorithms for Computational Biology - 4th International Conference, AlCoB 2017, Aveiro, Portugal, June 5-6, 2017, Proceedings, pages 127-139, 2017. URL: https://doi.org/10.1007/978-3-319-58163-7_9.
  25. Roderic D. M. Page. Maps between trees and cladistic analysis of historical associations among genes, organisms, and areas. Systematic Biology, 43(1):58-77, 1994. URL: https://doi.org/10.1093/sysbio/43.1.58.
  26. Pamela M. Pennington, Louisa Alexandra Messenger, Jeffrey Reina, José G. Juárez, Gena G. Lawrence, Ellen M. Dotson, Martin S. Llewellyn, and Celia Cordón-Rosales. The chagas disease domestic transmission cycle in guatemala: Parasite-vector switches and lack of mitochondrial co-diversification between triatoma dimidiata and trypanosoma cruzi subpopulations suggest non-vectorial parasite dispersal across the motagua valley. Acta Tropica, 151:80-87, 2015. Ecology and diversity of Trypanosoma cruzi. URL: https://doi.org/10.1016/j.actatropica.2015.07.014.
  27. Santi Santichaivekin, Ross Mawhorter, and Ran Libeskind-Hadas. An efficient exact algorithm for computing all pairwise distances between reconciliations in the duplication-transfer-loss model. BMC Bioinformatics, 20(20):636, 2019. URL: https://doi.org/10.1186/s12859-019-3203-9.
  28. Santi Santichaivekin, Qing Yang, Jingyi Liu, Ross Mawhorter, Justin Jiang, Trenton Wesley, Yi-Chieh Wu, and Ran Libeskind-Hadas. eMPRess: a systematic cophylogeny reconciliation tool. Bioinformatics, November 2020. URL: https://doi.org/10.1093/bioinformatics/btaa978.
  29. Celine Scornavacca, Wojciech Paprotny, Vincent Berry, and Vincent Ranwez. Representing a set of reconciliations in a compact way. Journal of Bioinformatics and Computational Biology, 11(02):1250025, 2013. URL: https://doi.org/10.1142/S0219720012500254.
  30. Patrícia M. Simões. Diversity and dynamics of Wolbachia-host associations in arthropods from the Society archipelago, French Polynesia. PhD thesis, University of Lyon 1, France, 2012. URL: https://tel.archives-ouvertes.fr/tel-00850707/file/SimoesP2012.pdf.
  31. Patrícia M. Simões, Gladys Mialdea, Daphné Reiss, Marie-France Sagot, and Sylvain Charlat. Wolbachia detection: an assessment of standard PCR protocols. Molecular Ecology Resources, 11(3):567-572, 2011. URL: https://doi.org/10.1111/j.1755-0998.2010.02955.x.
  32. Maureen Stolzer, Han Lai, Minli Xu, Deepa Sathaye, Benjamin Vernot, and Dannie Durand. Inferring duplications, losses, transfers and incomplete lineage sorting with nonbinary species trees. Bioinformatics, 28(18):i409-i415, September 2012. URL: https://doi.org/10.1093/bioinformatics/bts386.
  33. Yishu Wang, Arnaud Mary, Marie-France Sagot, and Blerina Sinaimeri. Capybara: equivalence class enumeration of cophylogeny event-based reconciliations. Bioinformatics, 36(14):4197-4199, 2020. URL: https://doi.org/10.1093/bioinformatics/btaa498.
  34. Yishu Wang, Arnaud Mary, Marie-France Sagot, and Blerina Sinaimeri. A general framework for enumerating equivalence classes of solutions, 2021. (submitted). URL: http://arxiv.org/abs/2004.12143.
  35. Nicolas Wieseke, Matthias Bernt, and Martin Middendorf. Unifying parsimonious tree reconciliation. In Algorithms in Bioinformatics - 13th International Workshop, WABI 2013, Proceedings, volume 8126 of Lecture Notes in Computer Science, pages 200-214, Berlin, Heidelberg, 2013. Springer. URL: https://doi.org/10.1007/978-3-642-40453-5_16.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact