Top

Published in:

2020 | OriginalPaper | Chapter

Checking Phylogenetic Decisiveness in Theory and in Practice

Authors : Ghazaleh Parvini, Katherine Braught, David Fernández-Baca

Published in: Bioinformatics Research and Applications

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Suppose we have a set X consisting of n taxa and we are given information from k loci from which to construct a phylogeny for X. Each locus offers information for only a fraction of the taxa. The question is whether this data suffices to construct a reliable phylogeny. The decisiveness problem expresses this question combinatorially. Although a precise characterization of decisiveness is known, the complexity of the problem is open. Here we relate decisiveness to a hypergraph coloring problem. We use this idea to (1) obtain lower bounds on the amount of coverage needed to achieve decisiveness, (2) devise an exact algorithm for decisiveness, (3) develop problem reduction rules, and use them to obtain efficient algorithms for inputs with few loci, and (4) devise an integer linear programming formulation of the decisiveness problem, which allows us to analyze data sets that arise in practice.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter MiRNA-Disease Associations Prediction Based on Negative Sample Selection and Multi-layer Perceptron

next chapter TNet: Phylogeny-Based Inference of Disease Transmission Networks Using Within-Host Strain Diversity

The \(O^*\)-notation is a variant of O-notation that ignores polynomial factors [8].

For an introduction to the applications of integer linear programming, see [12].

Ané, C., Eulenstein, O., Piaggio-Talice, R., Sanderson, M.J.: Groves of phylogenetic trees. Ann. Comb. 13(2), 139–167 (2009)CrossRef

Berge, C.: Graphs and Hypergraphs. North-Holland, Amsterdam (1973)

Berge, C.: Hypergraphs: Combinatorics of Finite Sets. North-Holland Mathematical Library, vol. 45. Elsevier (1984)

Bininda-Emonds, O.R.P. (ed.): Phylogenetic Supertrees: Combining Information to Reveal the Tree of Life, Series on Computational Biology, vol. 4. Springer, Berlin (2004)

Bodirsky, M., Kára, J., Martin, B.: The complexity of surjective homomorphism problems–a survey. Discrete Appl. Math. 160(12), 1680–1690 (2012)CrossRef

Dobrin, B.H., Zwickl, D.J., Sanderson, M.J.: The prevalence of terraced treescapes in analyses of phylogenetic data sets. BMC Evol. Biol. 18, 46 (2018)PubMedPubMedCentralCrossRef

Fischer, M.: Mathematical aspects of phylogenetic groves. Ann. Comb. 17(2), 295–310 (2013)CrossRef

Fomin, F.V., Kratsch, D.: Exact Exponential Algorithms. Springer, Heidelberg (2010)CrossRef

Graham, R.L., Knuth, D.E., Patashnik, O.: Concrete Mathematics: A Foundation for Computer Science. Addison-Wesley, Reading (1989)

10.

Guindon, S., Gascuel, O.: A simple, fast, and accurate algorithm to estimate large phylogenies by maximum likelihood. Syst. Biol. 52(5), 696–704 (2003)PubMedCrossRef

11.

Gurobi Optimization, LLC: Gurobi optimizer reference manual (2019). http://www.gurobi.com

12.

Gusfield, D.: Integer Linear Programming in Computational and Systems Biology: An Entry-level Text and Course. Cambridge University Press, New York (2019)CrossRef

13.

Hinchliff, C.E., et al.: Synthesis of phylogeny and taxonomy into a comprehensive tree of life. Proc. Natl. Acad. Sci. 112(41), 12764–12769 (2015). https://doi.org/10.1073/pnas.1423041112PubMedCrossRefPubMedCentral

14.

Jarvis, E.D., et al.: Whole-genome analyses resolve early branches in the tree of life of modern birds. Science 346(6215), 1320–1331 (2014)PubMedPubMedCentralCrossRef

15.

Parvini, G., Braught, K., Fernández-Baca, D.: Checking phylogenetic decisiveness in theory and in practice, February 2020. arXiv preprint https://arxiv.org/abs/2002.09722

16.

Sanderson, M.J., McMahon, M.M., Steel, M.: Phylogenomics with incomplete taxon coverage: the limits to inference. BMC Evol. Biol. 10, 155 (2010). https://doi.org/10.1186/1471-2148-10-155PubMedPubMedCentralCrossRef

17.

Sanderson, M.J., McMahon, M.M., Steel, M.: Terraces in phylogenetic tree space. Science 333(6041), 448–450 (2011). https://doi.org/10.1126/science.1206357, http://science.sciencemag.org/content/333/6041/448

18.

Scornavacca, C.: Supertree methods for phylogenomics. Ph.D. thesis, Univ. of Montpellier II, Montpellier, France, December 2009

19.

Semple, C., Steel, M.: Phylogenetics. Oxford Lecture Series in Mathematics. Oxford University Press, Oxford (2003)

20.

Stamatakis, A.: RAxML version 8: a tool for phylogenetic analysis and post-analysis of large phylogenies. Bioinformatics 30(9), 1312–1313 (2014)PubMedPubMedCentralCrossRef

21.

Stamatakis, A., Alachiotis, N.: Time and memory efficient likelihood-based tree searches on phylogenomic alignments with missing data. Bioinformatics 26(12), i132–i139 (2010)PubMedPubMedCentralCrossRef

22.

Steel, M.: Phylogeny: Discrete and Random Processes in Evolution. CBMS-NSF Conference Series in Applied Mathematics, vol. 89. SIAM, Philadelphia (2016)CrossRef

23.

Steel, M., Sanderson, M.J.: Characterizing phylogenetically decisive taxon coverage. Appl. Math. Lett. 23(1), 82–86 (2010)CrossRef

24.

Warnow, T.: Supertree construction: opportunities and challenges. Technical report, arXiv:1805.03530, ArXiV, May 2018. https://arxiv.org/abs/1805.03530

25.

Wickett, N.J., et al.: Phylotranscriptomic analysis of the origin and early diversification of land plants. Proc. Natl. Acad. Sci. 111(45), E4859–E4868 (2014)PubMedCrossRefPubMedCentral

26.

Wilkinson, M.: Coping with abundant missing entries in phylogenetic inference using parsimony. Syst. Biol. 44(4), 501–514 (1995)CrossRef

27.

Zhbannikov, I.Y., Brown, J.W., Foster, J.A.: decisivatoR: an R infrastructure package that addresses the problem of phylogenetic decisiveness. In: Proceedings of the International Conference on Bioinformatics, Computational Biology and Biomedical Informatics, pp. 716–717 (2013)

28.

Zhuk, D.: No-rainbow problem is NP-hard, March 2020. arXiv preprint https://arxiv.org/abs/2003.11764

Title: Checking Phylogenetic Decisiveness in Theory and in Practice
Authors: Ghazaleh Parvini
Katherine Braught
David Fernández-Baca
Publisher: Springer International Publishing
Book: Bioinformatics Research and Applications
Print ISBN: 978-3-030-57820-6

Electronic ISBN: 978-3-030-57821-3

Copyright Year: 2020
DOI: https://doi.org/10.1007/978-3-030-57821-3_17

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner