Document Open Access Logo

A New Paradigm for Identifying Reconciliation-Scenario Altering Mutations Conferring Environmental Adaptation

Authors Roni Zoller, Meirav Zehavi, Michal Ziv-Ukelson

PDF
Thumbnail PDF

File

LIPIcs.WABI.2019.9.pdf
  • Filesize: 0.64 MB
  • 13 pages

Document Identifiers

Author Details

Roni Zoller
  • Ben Gurion University of the Negev, Israel
Meirav Zehavi
  • Ben Gurion University of the Negev, Israel
Michal Ziv-Ukelson
  • Ben Gurion University of the Negev, Israel

Funding

Supported by ISF grants no. 1176/18 and no. 939/18. This work was supported by the Lynn and William Frankel Center for Computer Science.

Acknowledgements

We thank the anonymous WABI reviewers for very helpful comments.

Cite As Get BibTex

Roni Zoller, Meirav Zehavi, and Michal Ziv-Ukelson. A New Paradigm for Identifying Reconciliation-Scenario Altering Mutations Conferring Environmental Adaptation. In 19th International Workshop on Algorithms in Bioinformatics (WABI 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 143, pp. 9:1-9:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.WABI.2019.9

Abstract

An important goal in microbial computational genomics is to identify crucial events in the evolution of a gene that severely alter the duplication, loss and mobilization patterns of the gene within the genomes in which it disseminates. In this paper, we formalize this microbiological goal as a new pattern-matching problem in the domain of Gene tree and Species tree reconciliation, denoted "Reconciliation-Scenario Altering Mutation (RSAM) Discovery". We propose an O(m * n * k) time algorithm to solve this new problem, where m and n are the number of vertices of the input Gene tree and Species tree, respectively, and k is a user-specified parameter that bounds from above the number of optimal solutions of interest. The algorithm first constructs a hypergraph representing the k highest scoring reconciliation scenarios between the given Gene tree and Species tree, and then interrogates this hypergraph for subtrees matching a pre-specified RSAM Pattern. Our algorithm is optimal in the sense that the number of hypernodes in the hypergraph can be lower bounded by Omega(m * n * k). We implement the new algorithm as a tool, denoted RSAM-finder, and demonstrate its application to the identification of RSAMs in toxins and drug resistance elements across a dataset spanning hundreds of species.

Subject Classification

ACM Subject Classification
  • Applied computing → Bioinformatics
Keywords
  • Gene tree
  • Species tree
  • Reconciliation

Metrics

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

Supplementary Materials

References

  1. L E Alksne and B A Rasmussen. Expression of the AsbA1, OXA-12, and AsbM1 beta-lactamases in Aeromonas jandaei AER 14 is coordinated by a two-component regulon. Journal of bacteriology, 179(6):2006-2013, 1997. Google Scholar
  2. Timothy L Bailey, Nadya Williams, Chris Misleh, and Wilfred W Li. MEME: discovering and analyzing DNA and protein sequence motifs. Nucleic acids research, 34(suppl_2):W369-W373, 2006. Google Scholar
  3. M S Bansal, E J Alm, and M Kellis. Efficient algorithms for the reconciliation problem with gene duplication, horizontal transfer and loss. Bioinformatics, 28(12):i283-i291, 2012. Google Scholar
  4. M S Bansal, E J Alm, and M Kellis. Reconciliation revisited: Handling multiple optima when reconciling with duplication, transfer, and loss. Journal of Computational Biology, 20(10):738-754, 2013. Google Scholar
  5. E Bapteste, M A O'Malley, R G Beiko, M Ereshefsky, J P Gogarten, L Franklin-Hall, F-J Lapointe, J Dupré, T Dagan, Y Boucher, et al. Prokaryotic evolution and the tree of life are two different things. Biology direct, 4(1):34, 2009. Google Scholar
  6. V Berry, F Chevenet, J-P Doyon, and E Jousselin. A geography-aware reconciliation method to investigate diversification patterns in host/parasite interactions. Molecular ecology resources, 18(5):1173-1184, 2018. Google Scholar
  7. Baundauna Bose, Jennifer M Auchtung, Catherine A Lee, and Alan D Grossman. A conserved anti-repressor controls horizontal gene transfer by proteolysis. Molecular microbiology, 70(3):570-582, 2008. Google Scholar
  8. C Brandt, S D Braun, C Stein, P Slickers, R Ehricht, M W Pletz, and O Makarewicz. In silico serine β-lactamases analysis reveals a huge potential resistome in environmental and pathogenic species. Scientific reports, 7:43232, 2017. Google Scholar
  9. K Bush. Past and present perspectives on β-lactamases. Antimicrobial agents and chemotherapy, 62(10):e01076-18, 2018. Google Scholar
  10. MA Charleston. Jungles: a new solution to the host/parasite phylogeny reconciliation problem. Mathematical biosciences, 149(2):191-223, 1998. Google Scholar
  11. R Kumar Chaudhary, G Singh, R Naraian, and S Ram. Structural and functional in-silicoanalysis of toxin-antitoxin proteins in persister cells of pseudomonas aeruginosa. Plant Archives, 18(2):1643-1651, 2018. Google Scholar
  12. L A David and E J Alm. Rapid evolutionary innovation during an Archaean genetic expansion. Nature, 469(7328):93, 2011. Google Scholar
  13. B Donati, C Baudet, B Sinaimeri, P Crescenzi, and MF Sagot. EUCALYPT: efficient tree reconciliation enumerator. Algorithms for Molecular Biology, 10(1):3, 2015. Google Scholar
  14. J-P Doyon, C Chauve, and S Hamel. Space of gene/species trees reconciliations and parsimonious models. Journal of Computational Biology, 16(10):1399-1418, 2009. Google Scholar
  15. J-P Doyon, S Hamel, and C Chauve. An efficient method for exploring the space of gene tree/species tree reconciliations in a probabilistic framework. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 9(1):26-39, 2011. Google Scholar
  16. B A Evans and S GB Amyes. OXA β-lactamases. Clinical microbiology reviews, 27(2):241-263, 2014. Google Scholar
  17. L Huang and D Chiang. Better k-best parsing. In Proceedings of the Ninth International Workshop on Parsing Technology, pages 53-64. Association for Computational Linguistics, 2005. Google Scholar
  18. J Huerta-Cepas, F Serra, and P Bork. ETE 3: reconstruction, analysis, and visualization of phylogenomic data. Molecular biology and evolution, 33(6):1635-1638, 2016. Google Scholar
  19. R Libeskind-Hadas and M A Charleston. On the computational complexity of the reticulate cophylogeny reconstruction problem. Journal of Computational Biology, 16(1):105-117, 2009. Google Scholar
  20. A Marchler-Bauer and S H Bryant. CD-Search: protein domain annotations on the fly. Nucleic acids research, 32(suppl_2):W327-W331, 2004. Google Scholar
  21. O Massidda, M P Montanari, M Mingoia, and P E Varaldo. Borderline methicillin-susceptible Staphylococcus aureus strains have more in common than reduced susceptibility to penicillinase-resistant penicillins. Antimicrobial agents and chemotherapy, 40(12):2769-2774, 1996. Google Scholar
  22. D Merkle, M Middendorf, and N Wieseke. A parameter-adaptive dynamic programming approach for inferring cophylogenies. BMC bioinformatics, 11(1):S60, 2010. Google Scholar
  23. S Mukherjee, D Stamatis, J Bertsch, G Ovchinnikova, O Verezemska, M Isbandi, A D Thomas, R Ali, K Sharma, N C Kyrpides, et al. Genomes OnLine Database (GOLD) v. 6: data updates and feature enhancements. Nucleic acids research, page gkw992, 2016. Google Scholar
  24. R Patro and C Kingsford. Predicting protein interactions via parsimonious network history inference. Bioinformatics, 29(13):i237-i246, 2013. Google Scholar
  25. L Poirel, A Carrër, J D Pitout, and P Nordmann. Integron mobilization unit as a source of mobility of antibiotic resistance genes. Antimicrobial agents and chemotherapy, 53(6):2492-2498, 2009. Google Scholar
  26. A-A Popescu, K T Huber, and E Paradis. ape 3.0: New tools for distance-based phylogenetics and evolutionary analysis in R. Bioinformatics, 28(11):1536-1537, 2012. Google Scholar
  27. C Scornavacca, W Paprotny, V Berry, and V Ranwez. Representing a set of reconciliations in a compact way. Journal of bioinformatics and computational biology, 11(02):1250025, 2013. Google Scholar
  28. F Sievers and D G Higgins. Clustal Omega for making accurate alignments of many protein sequences. Protein Science, 27(1):135-145, 2018. Google Scholar
  29. P JM Stapleton, M Murphy, N McCallion, M Brennan, R Cunney, and R J Drew. Outbreaks of extended spectrum beta-lactamase-producing Enterobacteriaceae in neonatal intensive care units: a systematic review. Archives of Disease in Childhood-Fetal and Neonatal Edition, 101(1):72-78, 2016. Google Scholar
  30. M Stolzer, H Lai, M Xu, D Sathaye, B Vernot, and D Durand. Inferring duplications, losses, transfers and incomplete lineage sorting with nonbinary species trees. Bioinformatics, 28(18):i409-i415, 2012. Google Scholar
  31. J Sukumaran and M T Holder. DendroPy: a Python library for phylogenetic computing. Bioinformatics, 26(12):1569-1571, 2010. Google Scholar
  32. D Szklarczyk, J H Morris, H Cook, M Kuhn, S Wyder, M Simonovic, A Santos, N T Doncheva, A Roth, P Bork, et al. The STRING database in 2017: quality-controlled protein-protein association networks, made broadly accessible. Nucleic acids research, page gkw937, 2016. Google Scholar
  33. R L Tatusov, M Y Galperin, D A Natale, and E V Koonin. The COG database: a tool for genome-scale analysis of protein functions and evolution. Nucleic acids research, 28(1):33-36, 2000. Google Scholar
  34. TH To, E Jacox, V Ranwez, and C Scornavacca. A fast method for calculating reliable event supports in tree reconciliations via Pareto optimality. BMC bioinformatics, 16(1):384, 2015. Google Scholar
  35. A Tofigh. Using trees to capture reticulate evolution: lateral gene transfers and cancer progression. PhD thesis, KTH, 2009. Google Scholar
  36. A Tofigh, M Hallett, and J Lagergren. Simultaneous identification of duplications and lateral gene transfers. IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), 8(2):517-535, 2011. Google Scholar
  37. M Toth, N T Antunes, N K Stewart, H Frase, M Bhattacharya, C A Smith, and S B Vakulenko. Class D β-lactamases do exist in Gram-positive bacteria. Nature chemical biology, 12(1):9, 2016. Google Scholar
  38. L Van Melderen and M S De Bast. Bacterial toxin-antitoxin systems: more than selfish entities? PLoS genetics, 5(3):e1000437, 2009. 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