Document Open Access Logo

Detecting Locus Acquisition Events in Gene Trees

Authors Michal Aleksander Ciach, Anna Muszewska, Pawel Górecki

PDF
Thumbnail PDF

File

LIPIcs.WABI.2017.5.pdf
  • Filesize: 2.54 MB
  • 13 pages

Document Identifiers

Author Details

Michal Aleksander Ciach
Anna Muszewska
Pawel Górecki

Cite As Get BibTex

Michal Aleksander Ciach, Anna Muszewska, and Pawel Górecki. Detecting Locus Acquisition Events in Gene Trees. In 17th International Workshop on Algorithms in Bioinformatics (WABI 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 88, pp. 5:1-5:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.WABI.2017.5

Abstract

Horizontal Gene Transfer (HGT), a process of acquisition and fixation of foreign genetic material, is an important biological phenomenon. Several approaches to HGT inference have been proposed. However, most of them either rely on approximate, non-phylogenetic methods or on the tree reconciliation, which is computationally intensive and sensitive to parameter values. In this work, we investigate the Locus Tree Inference problem as a possible alternative that combines the advantages of both approaches. We show several algorithms to solve the problem in the parsimony framework. We introduce a novel tree mapping, which allows us to obtain a heuristic solution to the problems of locus tree inference and duplication classification. Our approach allows not only for faster comparisons of gene and species trees but also to improve known algorithms for duplication inference in the presence of polytomies in the species trees.

Subject Classification

Keywords
  • rank
  • taxon
  • ranked species tree
  • speciation
  • gene duplication
  • gene loss
  • horizontal gene transfer

Metrics

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

References

  1. 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
  2. Michael A. Bender and Martin Farach-Colton. The LCA problem revisited. In Latin American Symposium on Theoretical Informatics, pages 88-94. Springer, 2000. Google Scholar
  3. Ann-Charlotte Berglund-Sonnhammer, Pär Steffansson, Matthew J. Betts, and David A. Liberles. Optimal gene trees from sequences and species trees using a soft interpretation of parsimony. Journal of Molecular Evolution, 63(2):240-250, 2006. Google Scholar
  4. P. Bonizzoni, G. Della Vedova, and R. Dondi. Reconciling a gene tree to a species tree under the duplication cost model. Theoretical Computer Science, 347(1-2):36-53, 2005. Google Scholar
  5. Jean-Philippe Doyon, Vincent Ranwez, Vincent Daubin, and Vincent Berry. Models, algorithms and programs for phylogeny reconciliation. Briefings in Bioinformatics, 12(5):392, 2011. Google Scholar
  6. O. Eulenstein, S. Huzurbazar, and D. A. Liberles. Evolution after Gene Duplication, chapter Reconciling Phylogenetic Trees, pages 185-206. John Wiley &Sons, Inc., 2010. Google Scholar
  7. P. Górecki and J. Tiuryn. DLS-trees: A model of evolutionary scenarios. Theoretical Computer Science, 359(1-3):378-399, 2006. Google Scholar
  8. Patrick J. Keeling and Jeffrey D. Palmer. Horizontal gene transfer in eukaryotic evolution. Nature Reviews Genetics, 9(8):605-618, 2008. Google Scholar
  9. Manuel Lafond, Krister M. Swenson, and Nadia El-Mabrouk. An optimal reconciliation algorithm for gene trees with polytomies. In International Workshop on Algorithms in Bioinformatics, pages 106-122. Springer, 2012. Google Scholar
  10. Marina Marcet-Houben and Toni Gabaldón. Treeko: a duplication-aware algorithm for the comparison of phylogenetic trees. Nucleic Acids Research, page gkr087, 2011. Google Scholar
  11. Miguel A Naranjo-Ortíz, Matthias Brock, Sascha Brunke, Bernhard Hube, Marina Marcet-Houben, and Toni Gabaldón. Widespread inter-and intra-domain horizontal gene transfer of d-amino acid metabolism enzymes in eukaryotes. Frontiers in Microbiology, 7, 2016. Google Scholar
  12. 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. Google Scholar
  13. Matthew D. Rasmussen and Manolis Kellis. Unified modeling of gene duplication, loss, and coalescence using a locus tree. Genome Research, 22(4):755-765, 2012. Google Scholar
  14. Matt Ravenhall, Nives Škunca, Florent Lassalle, and Christophe Dessimoz. Inferring horizontal gene transfer. PLOS Computational Biology, 11(5):1-16, 05 2015. Google Scholar
  15. Thomas A. Richards, Guy Leonard, Darren M. Soanes, and Nicholas J. Talbot. Gene transfer into the fungi. Fungal Biology Reviews, 25(2):98-110, 2011. Google Scholar
  16. M. J. Sanderson and M. M. McMahon. Inferring angiosperm phylogeny from EST data with widespread gene duplication. BMC Evolutionary Biology, 7 (Suppl 1): S3, 2007. Google Scholar
  17. 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, 2012. Google Scholar
  18. Benjamin Vernot, Maureen Stolzer, Aiton Goldman, and Dannie Durand. Reconciliation with non-binary species trees. Journal of Computational Biology, 15(8):981-1006, 2008. Google Scholar
  19. Tandy Warnow. Large-scale multiple sequence alignment and phylogeny estimation. In Models and Algorithms for Genome Evolution, pages 85-146. Springer, 2013. Google Scholar
  20. Yu Zheng and Louxin Zhang. Reconciliation with non-binary gene trees revisited. In International Conference on Research in Computational Molecular Biology, pages 418-432. Springer, 2014. 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