Document Open Access Logo

Predicting Horizontal Gene Transfers with Perfect Transfer Networks

Authors Alitzel López Sánchez, Manuel Lafond

PDF
Thumbnail PDF

File

LIPIcs.WABI.2022.3.pdf
  • Filesize: 0.78 MB
  • 22 pages

Document Identifiers

Author Details

Alitzel López Sánchez
  • Computer Science Department, Université de Sherbrooke, Canada
Manuel Lafond
  • Computer Science Department, Université de Sherbrooke, Canada

Funding

  • López Sánchez, Alitzel: acknowledges financial support from the programme de bourses d'excellence en recherche from the University of Sherbrooke.
  • Lafond, Manuel: acknowledges financial support from the Natural Sciences and Engineering Research Council (NSERC) and the Fonds de Recherche du Québec Nature et technologies (FRQNT).

Acknowledgements

The authors would like to thank the reviewers for their helpful comments and for pointing out paper [Nakhleh, 2004].

Cite As Get BibTex

Alitzel López Sánchez and Manuel Lafond. Predicting Horizontal Gene Transfers with Perfect Transfer Networks. In 22nd International Workshop on Algorithms in Bioinformatics (WABI 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 242, pp. 3:1-3:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.WABI.2022.3

Abstract

Horizontal gene transfer inference approaches are usually based on gene sequences: parametric methods search for patterns that deviate from a particular genomic signature, while phylogenetic methods use sequences to reconstruct the gene and species trees. However, it is well-known that sequences have difficulty identifying ancient transfers since mutations have enough time to erase all evidence of such events. In this work, we ask whether character-based methods can predict gene transfers. Their advantage over sequences is that homologous genes can have low DNA similarity, but still have retained enough important common motifs that allow them to have common character traits, for instance the same functional or expression profile. A phylogeny that has two separate clades that acquired the same character independently might indicate the presence of a transfer even in the absence of sequence similarity.
We introduce perfect transfer networks, which are phylogenetic networks that can explain the character diversity of a set of taxa. This problem has been studied extensively in the form of ancestral recombination networks, but these only model hybridation events and do not differentiate between direct parents and lateral donors. We focus on tree-based networks, in which edges representing vertical descent are clearly distinguished from those that represent horizontal transmission. Our model is a direct generalization of perfect phylogeny models to such networks. Our goal is to initiate a study on the structural and algorithmic properties of perfect transfer networks. We then show that in polynomial time, one can decide whether a given network is a valid explanation for a set of taxa, and show how, for a given tree, one can add transfer edges to it so that it explains a set of taxa.

Subject Classification

ACM Subject Classification
  • Applied computing → Molecular evolution
Keywords
  • Horizontal gene transfer
  • tree-based networks
  • perfect phylogenies
  • character-based
  • gene-expression
  • indirect phylogenetic methods

Metrics

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

References

  1. Patrick A Alexander, Yanan He, Yihong Chen, John Orban, and Philip N Bryan. The design and characterization of two proteins with 88% sequence identity but different structure and function. Proceedings of the National Academy of Sciences, 104(29):11963-11968, 2007. Google Scholar
  2. Yoann Anselmetti, Nadia El-Mabrouk, Manuel Lafond, and Aïda Ouangraoua. Gene tree and species tree reconciliation with endosymbiotic gene transfer. Bioinformatics, 37(Supplement_1):i120-i132, 2021. Google Scholar
  3. Eliran Avni and Sagi Snir. A new phylogenomic approach for quantifying horizontal gene transfer trends in prokaryotes. Scientific reports, 10(1):1-14, 2020. Google Scholar
  4. Vineet Bafna, Dan Gusfield, Giuseppe Lancia, and Shibu Yooseph. Haplotyping as perfect phylogeny: A direct approach. Journal of Computational Biology, 10(3-4):323-340, 2003. Google Scholar
  5. Mukul S Bansal, Eric J Alm, and Manolis Kellis. Efficient algorithms for the reconciliation problem with gene duplication, horizontal transfer and loss. Bioinformatics, 28(12):i283-i291, 2012. Google Scholar
  6. Hans L Bodlaender, Mike R Fellows, and Tandy J Warnow. Two strikes against perfect phylogeny. In International Colloquium on Automata, Languages, and Programming, pages 273-283. Springer, 1992. Google Scholar
  7. Magnus Bordewich and Charles Semple. A universal tree-based network with the minimum number of reticulations. Discrete Applied Mathematics, 250:357-362, 2018. Google Scholar
  8. Luis Boto. Horizontal gene transfer in evolution: facts and challenges. Proceedings of the Royal Society B: Biological Sciences, 277(1683):819-827, 2010. Google Scholar
  9. Joseph H. Camin and Robert R. Sokal. A method for deducing branching sequences in phylogeny. Evolution, 19(3):311, September 1965. URL: https://doi.org/10.2307/2406441.
  10. Gjalt De Jong. Phenotypic plasticity as a product of selection in a variable environment. The American Naturalist, 145(4):493-512, 1995. Google Scholar
  11. Mattéo Delabre, Nadia El-Mabrouk, Katharina T Huber, Manuel Lafond, Vincent Moulton, Emmanuel Noutahi, and Miguel Sautie Castellanos. Evolution through segmental duplications and losses: a super-reconciliation approach. Algorithms for Molecular Biology, 15(1):1-15, 2020. Google Scholar
  12. Gianluca Della Vedova, Murray Patterson, Raffaella Rizzi, and Mauricio Soto. Character-based phylogeny construction and its application to tumor evolution. In Conference on Computability in Europe, pages 3-13. Springer, 2017. Google Scholar
  13. Jean-Philippe Doyon, Celine Scornavacca, K Yu Gorbunov, Gergely J Szöllősi, Vincent Ranwez, and Vincent Berry. An efficient algorithm for gene/species trees parsimonious reconciliation with losses, duplications and transfers. In RECOMB international workshop on comparative genomics, pages 93-108. Springer, 2010. Google Scholar
  14. James S. Farris. Phylogenetic Analysis Under Dollo’s Law. Systematic Biology, 26(1):77-88, March 1977. URL: https://doi.org/10.1093/sysbio/26.1.77.
  15. Joseph Felsenstein. Inferring phylogenies. Sunderland, Mass. : Sinauer Associates, 2004. Google Scholar
  16. David Fernández-Baca. The perfect phylogeny problem. In Steiner Trees in Industry, pages 203-234. Springer, 2001. Google Scholar
  17. Andrew Francis, Charles Semple, and Mike Steel. New characterisations of tree-based networks and proximity measures. Advances in Applied Mathematics, 93:93-107, 2018. URL: https://doi.org/10.1016/j.aam.2017.08.003.
  18. Andrew R Francis and Mike Steel. Which phylogenetic networks are merely trees with additional arcs? Systematic Biology, 64(5):768-777, 2015. Google Scholar
  19. Manuela Geiß, John Anders, Peter F Stadler, Nicolas Wieseke, and Marc Hellmuth. Reconstructing gene trees from fitch’s xenology relation. Journal of Mathematical Biology, 77(5):1459-1491, 2018. Google Scholar
  20. Dan Gusfield. The multi-state perfect phylogeny problem with missing and removable data: Solutions via integer-programming and chordal graph theory. Journal of Computational Biology, 17(3):383-399, March 2010. URL: https://doi.org/10.1089/cmb.2009.0200.
  21. Dan Gusfield. ReCombinatorics: the algorithmics of ancestral recombination graphs and explicit phylogenetic networks. MIT press, 2014. Google Scholar
  22. Dan Gusfield, Satish Eddhu, and Charles Langley. Optimal, efficient reconstruction of phylogenetic networks with constrained recombination. Journal of Bioinformatics and Computational Biology, 2(01):173-213, 2004. Google Scholar
  23. Marc Hellmuth, Katharina T Huber, and Vincent Moulton. Reconciling event-labeled gene trees with mul-trees and species networks. Journal of Mathematical Biology, 79(5):1885-1925, 2019. Google Scholar
  24. Marc Hellmuth, Carsten R Seemann, and Peter F Stadler. Generalized fitch graphs II: Sets of binary relations that are explained by edge-labeled trees. Discrete Applied Mathematics, 283:495-511, 2020. Google Scholar
  25. Julie C Dunning Hotopp. Horizontal gene transfer between bacteria and animals. Trends in genetics, 27(4):157-163, 2011. Google Scholar
  26. Leo Van Iersel, Mark Jones, and Steven Kelk. A third strike against perfect phylogeny. Systematic Biology, 68(5):814-827, 2019. Google Scholar
  27. Nicholas AT Irwin, Alexandros A Pittis, Thomas A Richards, and Patrick J Keeling. Systematic evaluation of horizontal gene transfer between eukaryotes and viruses. Nature microbiology, 7(2):327-336, 2022. Google Scholar
  28. Edwin Jacox, Mathias Weller, Eric Tannier, and Celine Scornavacca. Resolution and reconciliation of non-binary gene trees with transfers, duplications and losses. Bioinformatics, 33(7):980-987, 2017. Google Scholar
  29. Mark Jones, Manuel Lafond, and Celine Scornavacca. Consistency of orthology and paralogy constraints in the presence of gene transfers. Peer Community in Mathematical and Computational Biology, 2012. Google Scholar
  30. Patrick J Keeling and Jeffrey D Palmer. Horizontal gene transfer in eukaryotic evolution. Nature Reviews Genetics, 9(8):605-618, 2008. Google Scholar
  31. Eugene V Koonin, Kira S Makarova, and L Aravind. Horizontal gene transfer in prokaryotes: quantification and classification. Annual Reviews in Microbiology, 55(1):709-742, 2001. Google Scholar
  32. Misagh Kordi and Mukul S Bansal. On the complexity of duplication-transfer-loss reconciliation with non-binary gene trees. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 14(3):587-599, 2015. Google Scholar
  33. Manuel Lafond and Marc Hellmuth. Reconstruction of time-consistent species trees. Algorithms for Molecular Biology, 15(1):1-27, 2020. Google Scholar
  34. Salem Malikic, Farid Rashidi Mehrabadi, Simone Ciccolella, Md Khaledur Rahman, Camir Ricketts, Ehsan Haghshenas, Daniel Seidman, Faraz Hach, Iman Hajirasouliha, and S Cenk Sahinalp. Phiscs: a combinatorial approach for subperfect tumor phylogeny reconstruction via integrative use of single-cell and bulk sequencing data. Genome research, 29(11):1860-1877, 2019. Google Scholar
  35. Yukihiro Murakami. On Phylogenetic Encodings and Orchard Networks. PhD thesis, TU Delft, 2021. Google Scholar
  36. Luay Nakhleh. Phylogenetic networks. PhD thesis, The University of Texas at Austin, 2004. Google Scholar
  37. Luay Nakhleh, Don Ringe, and Tandy Warnow. Perfect phylogenetic networks: A new methodology for reconstructing the evolutionary history of natural languages. Language, 81(2):382-420, 2005. URL: http://www.jstor.org/stable/4489897.
  38. Joan Carles Pons, Charles Semple, and Mike Steel. Tree-based networks: characterisations, metrics, and support trees. Journal of Mathematical Biology, 78(4):899-918, October 2018. URL: https://doi.org/10.1007/s00285-018-1296-9.
  39. Joan Carles Pons, Charles Semple, and Mike Steel. Tree-based networks: characterisations, metrics, and support trees. Journal of Mathematical Biology, 78(4):899-918, 2019. Google Scholar
  40. Beatriz Pontes, Raúl Giráldez, and Jesús S Aguilar-Ruiz. Configurable pattern-based evolutionary biclustering of gene expression data. Algorithms for Molecular Biology, 8(1):1-22, 2013. Google Scholar
  41. Dikshant Pradhan and Mohammed El-Kebir. On the non-uniqueness of solutions to the perfect phylogeny mixture problem. In RECOMB International Conference on Comparative Genomics, pages 277-293. Springer, 2018. Google Scholar
  42. Matt Ravenhall, Nives Škunca, Florent Lassalle, and Christophe Dessimoz. Inferring horizontal gene transfer. PLoS Computational Biology, 11(5):e1004095, 2015. Google Scholar
  43. Arun Rawat, Georg J Seifert, and Youping Deng. Novel implementation of conditional co-regulation by graph theory to derive co-expressed genes from microarray data. In BMC Bioinformatics, volume 9, pages 1-9. Springer, 2008. Google Scholar
  44. Don Ringe, Tandy Warnow, and Ann Taylor. Indo-european and computational cladistics. Transactions of the Philological Society, 100(1):59-129, 2002. Google Scholar
  45. Michael J Sanderson and Larry Hufford. Homoplasy: the recurrence of similarity in evolution. Elsevier, 1996. Google Scholar
  46. Palash Sashittal, Simone Zaccaria, and Mohammed El-Kebir. Parsimonious clone tree reconciliation in cancer. In Leibniz International Proceedings in Informatics, LIPIcs, volume 201, page 9. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2021. Google Scholar
  47. David Schaller, Manuel Lafond, Peter F Stadler, Nicolas Wieseke, and Marc Hellmuth. Indirect identification of horizontal gene transfer. Journal of Mathematical Biology, 83(1):1-73, 2021. Google Scholar
  48. Charles Semple and Mike Steel. Tree reconstruction from multi-state characters. Advances in Applied Mathematics, 28(2):169-184, 2002. Google Scholar
  49. Christopher M Thomas and Kaare M Nielsen. Mechanisms of, and barriers to, horizontal gene transfer between bacteria. Nature Reviews Microbiology, 3(9):711-721, 2005. Google Scholar
  50. Ali Tofigh, Michael Hallett, and Jens Lagergren. Simultaneous identification of duplications and lateral gene transfers. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 8(2):517-535, 2010. Google Scholar
  51. Catalina Trejo-Becerril, Enrique Pérez-Cárdenas, Lucía Taja-Chayeb, Philippe Anker, Roberto Herrera-Goepfert, Luis A Medina-Velázquez, Alfredo Hidalgo-Miranda, Delia Pérez-Montiel, Alma Chávez-Blanco, Judith Cruz-Velázquez, et al. Cancer progression mediated by horizontal gene transfer in an in vivo model. PloS One, 7(12):e52754, 2012. Google Scholar
  52. Lusheng Wang, Kaizhong Zhang, and Louxin Zhang. Perfect phylogenetic networks with recombination. Journal of Computational Biology, 8(1):69-78, 2001. Google Scholar
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