Algorithms for genome-scale phylogenetics using gene tree parsimony

IEEE/ACM Transactions on Computational Biology and Bioinformatics
Mukul S Bansal, Oliver Eulenstein

Abstract

The use of genomic data sets for phylogenetics is complicated by the fact that evolutionary processes such as gene duplication and loss, or incomplete lineage sorting (deep coalescence) cause incongruence among gene trees. One well-known approach that deals with this complication is gene tree parsimony, which, given a collection of gene trees, seeks a species tree that requires the smallest number of evolutionary events to explain the incongruence of the gene trees. However, a lack of efficient algorithms has limited the use of this approach. Here, we present efficient algorithms for SPR and TBR-based local search heuristics for gene tree parsimony under the 1) duplication, 2) loss, 3) duplication-loss, and 4) deep coalescence reconciliation costs. These novel algorithms improve upon the time complexities of previous algorithms for these problems by a factor of n, where n is the number of species in the collection of gene trees. Our algorithms provide a substantial improvement in runtime and scalability compared to previous implementations and enable large-scale gene tree parsimony analyses using any of the four reconciliation costs. Our algorithms have been implemented in the software packages DupTree and iGTP, and have alread...Continue Reading

References

Jan 1, 1995·Journal of Computational Biology : a Journal of Computational Molecular Cell Biology·B MirkinT F Smith
Oct 1, 1996·Molecular Phylogenetics and Evolution·R GuigóT F Smith
Jul 1, 1997·Journal of Computational Biology : a Journal of Computational Molecular Cell Biology·L Zhang
Jan 13, 2000·Molecular Phylogenetics and Evolution·R D Page
Mar 2, 2006·Systematic Biology·Wayne P Maddison, L Lacey Knowles
Feb 10, 2007·BMC Evolutionary Biology·Michael J Sanderson, Michelle M McMahon
Mar 30, 2007·Proceedings of the National Academy of Sciences of the United States of America·Scott V EdwardsDennis K Pearl
Jun 15, 2007·Systematic Biology·James A Cotton, Mark Wilkinson
May 9, 2008·Evolution; International Journal of Organic Evolution·Liang LiuScott V Edwards
May 14, 2008·Bioinformatics·André WeheOliver Eulenstein
Sep 30, 2008·Molecular Biology and Evolution·Chih-Horng KuoJessica C Kissinger
Nov 8, 2008·IEEE/ACM Transactions on Computational Biology and Bioinformatics·Mukul S Bansal, Oliver Eulenstein
Feb 13, 2009·Bioinformatics·Laura S KubatkoL Lacey Knowles
Mar 14, 2009·Journal of Mathematical Biology·Liang LiuDennis K Pearl
Mar 21, 2009·Proceedings of the National Academy of Sciences of the United States of America·Orjan AkerborgJens Lagergren
May 2, 2009·IEEE/ACM Transactions on Computational Biology and Bioinformatics·Mukul S BansalAndré Wehe
May 26, 2009·The Veterinary Record·Jill Maddison
Sep 15, 2009·PLoS Computational Biology·Cuong Than, Luay Nakhleh
Nov 13, 2009·Molecular Biology and Evolution·Joseph Heled, Alexei J Drummond
Jun 9, 2010·Systematic Biology·Liang LiuScott V Edwards
Aug 25, 2010·IEEE/ACM Transactions on Computational Biology and Bioinformatics·Mukul S Bansal, Ron Shamir
Sep 24, 2010·Bioinformatics·Bret R LargetCécile Ané
Nov 26, 2010·BMC Bioinformatics·Ruchi ChaudharyOliver Eulenstein
Dec 28, 2010·Systematic Biology·J Gordon BurleighTodd J Vision
Jan 8, 2011·Journal of Computational Biology : a Journal of Computational Molecular Cell Biology·Cuong V Than, Noah A Rosenberg
Mar 5, 2011·BMC Bioinformatics·Wen-Chieh ChangOliver Eulenstein
Mar 5, 2011·BMC Bioinformatics·Pawel GóreckiOliver Eulenstein
Mar 15, 2011·Molecular Phylogenetics and Evolution·Helen Hang Fan, Laura S Kubatko
Mar 23, 2011·IEEE/ACM Transactions on Computational Biology and Bioinformatics·Yang XiangKun Huang
Mar 25, 2011·Advances in Experimental Medicine and Biology·Jean-Philippe Doyon, Cedric Chauve
May 18, 2011·IEEE/ACM Transactions on Computational Biology and Bioinformatics·Louxin Zhang
Jul 27, 2011·IEEE/ACM Transactions on Computational Biology and Bioinformatics·Paul Phipps, Sergey Bereg
Oct 5, 2011·IEEE/ACM Transactions on Computational Biology and Bioinformatics·Selim Mimaroglu, Emin Aksehirli
Nov 1, 2011·Journal of Computational Biology : a Journal of Computational Molecular Cell Biology·Yun YuLuay Nakhleh
Jan 6, 2012·Journal of Computational Biology : a Journal of Computational Molecular Cell Biology·Ethan M Jewett, Noah A Rosenberg
Jan 25, 2012·Genome Research·Matthew D Rasmussen, Manolis Kellis
Feb 15, 2012·IEEE/ACM Transactions on Computational Biology and Bioinformatics·Tommaso MazzaDavide Prandi
Feb 16, 2012·Systematic Biology·Laura A KatzJ Gordon Burleigh
Apr 18, 2012·IEEE/ACM Transactions on Computational Biology and Bioinformatics·John C HawkinsM Teresa Pisabarro

❮ Previous
Next ❯

Citations

Apr 4, 2014·Systematic Biology·Christopher WhiddenRobert G Beiko
Apr 29, 2016·Journal of Bioinformatics and Computational Biology·Jucheol MoonOliver Eulenstein
Oct 5, 2014·Systematic Biology·Leonardo De Oliveira MartinsDavid Posada
Aug 3, 2016·Philosophical Transactions of the Royal Society of London. Series B, Biological Sciences·Diego Mallo, David Posada
May 18, 2017·Journal of Bioinformatics and Computational Biology·Jucheol Moon, Oliver Eulenstein
Oct 30, 2020·BMC Evolutionary Biology·Paweł GóreckiOliver Eulenstein

❮ Previous
Next ❯

Related Concepts

Trending Feeds

COVID-19

Coronaviruses encompass a large family of viruses that cause the common cold as well as more serious diseases, such as the ongoing outbreak of coronavirus disease 2019 (COVID-19; formally known as 2019-nCoV). Coronaviruses can spread from animals to humans; symptoms include fever, cough, shortness of breath, and breathing difficulties; in more severe cases, infection can lead to death. This feed covers recent research on COVID-19.

Blastomycosis

Blastomycosis fungal infections spread through inhaling Blastomyces dermatitidis spores. Discover the latest research on blastomycosis fungal infections here.

Nuclear Pore Complex in ALS/FTD

Alterations in nucleocytoplasmic transport, controlled by the nuclear pore complex, may be involved in the pathomechanism underlying multiple neurodegenerative diseases including Amyotrophic Lateral Sclerosis and Frontotemporal Dementia. Here is the latest research on the nuclear pore complex in ALS and FTD.

Applications of Molecular Barcoding

The concept of molecular barcoding is that each original DNA or RNA molecule is attached to a unique sequence barcode. Sequence reads having different barcodes represent different original molecules, while sequence reads having the same barcode are results of PCR duplication from one original molecule. Discover the latest research on molecular barcoding here.

Chronic Fatigue Syndrome

Chronic fatigue syndrome is a disease characterized by unexplained disabling fatigue; the pathology of which is incompletely understood. Discover the latest research on chronic fatigue syndrome here.

Evolution of Pluripotency

Pluripotency refers to the ability of a cell to develop into three primary germ cell layers of the embryo. This feed focuses on the mechanisms that underlie the evolution of pluripotency. Here is the latest research.

Position Effect Variegation

Position Effect Variagation occurs when a gene is inactivated due to its positioning near heterochromatic regions within a chromosome. Discover the latest research on Position Effect Variagation here.

STING Receptor Agonists

Stimulator of IFN genes (STING) are a group of transmembrane proteins that are involved in the induction of type I interferon that is important in the innate immune response. The stimulation of STING has been an active area of research in the treatment of cancer and infectious diseases. Here is the latest research on STING receptor agonists.

Microbicide

Microbicides are products that can be applied to vaginal or rectal mucosal surfaces with the goal of preventing, or at least significantly reducing, the transmission of sexually transmitted infections. Here is the latest research on microbicides.