Section: Mathematical & Computational Biology
Topic: Biophysics and computational biology, Computer sciences, Applied mathematics

When Three Trees Go to War

van Iersel, Leo1  ; Jones, Mark1  ; Weller, Mathias2, 3   
1 Delft Institute of Applied Mathematics, Mekelweg 4, 2628 CD, Delft // POSTBUS 5031, 2600 GA Delft
2 Technical University of Berlin / Technische Universität Berlin, Straße des 17. Juni 135 10623 Berlin
3 Institut des sciences informatiques et de leurs interactions - CNRS Sciences informatiques, Centre National de la Recherche Scientifique, 3 Rue Michel Ange 75794 Paris Cedex 16 - France

10.24072/pcjournal.419 - Peer Community Journal, Volume 4 (2024), article no. e54.

Get full text PDF Peer reviewed and recommended by PCI
article image

How many reticulations are needed for a phylogenetic network to display a given set of k phylogenetic trees on n leaves? For k = 2, Baroni et al. [Ann. Comb. 8, 391-408 (2005)] showed that the answer is n − 2. Here, we show that, for k ≥ 3 the answer is at least (3 /2 − ε)n. Concretely, we prove that, for each ε > 0, there is some n ∈ N such that three n-leaf caterpillar trees can be constructed in such a way that any network displaying these caterpillars contains at least (3 /2 − ε)n reticulations. The case of three trees is interesting since it is the easiest case that cannot be equivalently formulated in terms of agreement forests. Instead, we base the result on a surprising lower bound for multilabelled trees (MUL-trees) displaying the caterpillars. Indeed, we show that one cannot do (more than an ε) better than the trivial MUL-tree resulting from a simple concatenation of the given caterpillars. The results are relevant for the development of methods for the Hybridization Number problem on more than two trees. This fundamental problem asks to construct a binary phylogenetic network with a minimum number of reticulations displaying a given set of phylogenetic trees.

Published online:
DOI: 10.24072/pcjournal.419
Type: Research article

van Iersel, Leo 1; Jones, Mark 1; Weller, Mathias 2, 3

1 Delft Institute of Applied Mathematics, Mekelweg 4, 2628 CD, Delft // POSTBUS 5031, 2600 GA Delft
2 Technical University of Berlin / Technische Universität Berlin, Straße des 17. Juni 135 10623 Berlin
3 Institut des sciences informatiques et de leurs interactions - CNRS Sciences informatiques, Centre National de la Recherche Scientifique, 3 Rue Michel Ange 75794 Paris Cedex 16 - France
License: CC-BY 4.0
Copyrights: The authors retain unrestricted copyrights and publishing rights 
@article{10_24072_pcjournal_419,
     author = {van Iersel, Leo and Jones, Mark and Weller, Mathias},
     title = {When {Three} {Trees} {Go} to {War}},
     journal = {Peer Community Journal},
     eid = {e54},
     publisher = {Peer Community In},
     volume = {4},
     year = {2024},
     doi = {10.24072/pcjournal.419},
     language = {en},
     url = {https://peercommunityjournal.org/articles/10.24072/pcjournal.419/}
}
TY  - JOUR
AU  - van Iersel, Leo
AU  - Jones, Mark
AU  - Weller, Mathias
TI  - When Three Trees Go to War
JO  - Peer Community Journal
PY  - 2024
VL  - 4
PB  - Peer Community In
UR  - https://peercommunityjournal.org/articles/10.24072/pcjournal.419/
DO  - 10.24072/pcjournal.419
LA  - en
ID  - 10_24072_pcjournal_419
ER  - 
%0 Journal Article
%A van Iersel, Leo
%A Jones, Mark
%A Weller, Mathias
%T When Three Trees Go to War
%J Peer Community Journal
%D 2024
%V 4
%I Peer Community In
%U https://peercommunityjournal.org/articles/10.24072/pcjournal.419/
%R 10.24072/pcjournal.419
%G en
%F 10_24072_pcjournal_419
van Iersel, Leo; Jones, Mark; Weller, Mathias. When Three Trees Go to War. Peer Community Journal, Volume 4 (2024), article  no. e54. doi : 10.24072/pcjournal.419. https://peercommunityjournal.org/articles/10.24072/pcjournal.419/

PCI peer reviews and recommendation, and links to data, scripts, code and supplementary information: 10.24072/pci.mcb.100187

Conflict of interest of the recommender and peer reviewers:
The recommender in charge of the evaluation of the article and the reviewers declared that they have no conflict of interest (as defined in the code of conduct of PCI) with the authors or with the content of the article.

[1] Baroni, M.; Grünewald, S.; Moulton, V.; Semple, C. Bounding the Number of Hybridisation Events for a Consistent Evolutionary History, Journal of mathematical biology, Volume 51 (2005), pp. 171-182 | DOI

[2] Baroni, M.; Semple, C.; Steel, M. A Framework for Representing Reticulate Evolution, Annals of Combinatorics, Volume 8 (2005), pp. 391-408 | DOI

[3] Bordewich, M.; Semple, C. Computing the Minimum Number of Hybridization Events for a Consistent Evolutionary History, Discrete Applied Mathematics, Volume 155 (2007) no. 8, pp. 914-928 | DOI

[4] Bordewich, M.; Semple, C. A Universal Tree-Based Network with the Minimum Number of Reticulations, Discrete Applied Mathematics, Volume 250 (2018), pp. 357-362 | DOI

[5] Dagan, T.; Artzy-Randrup, Y.; Martin, W. Modular Networks and Cumulative Impact of Lateral Transfer in Prokaryote Genome Evolution, Proceedings of the National Academy of Sciences, Volume 105 (2008) no. 29, pp. 10039-10044 | DOI

[6] Francis, A. R.; Steel, M. Which Phylogenetic Networks Are Merely Trees with Additional Arcs?, Systematic Biology, Volume 64 (2015) no. 5, pp. 768-777 | DOI

[7] Hayamizu, M. On the Existence of Infinitely Many Universal Tree-Based Networks, Journal of Theoretical Biology, Volume 396 (2016), pp. 204-206 | DOI

[8] Hunter, Z. Shortest Common Supersequence of Permutations – TCS StackExchange, 2023 (https://cstheory.stackexchange.com/questions/53153)

[9] Kelk, S.; van Iersel, L.; Lekic, N.; Linz, S.; Scornavacca, C.; Stougie, L. Cycle Killer... Qu'est-Ce Que c'est? On the Comparative Approximability of Hybridization Number and Directed Feedback Vertex Set, SIAM journal on discrete mathematics, Volume 26 (2012) no. 4, pp. 1635-1656 | DOI

[10] van Lersel, L.; Jones, M.; Weller, M. Embedding Phylogenetic Trees in Networks of Low Treewidth, 30th Annual European Symposium on Algorithms (ESA 2022) (Leibniz International Proceedings in Informatics (Lipics)), Volume 244, 2022, p. 69 | DOI

[11] van Lersel, L.; Kelk, S. When Two Trees Go to War, Journal of theoretical biology, Volume 269 (2011) no. 1, pp. 245-255 | DOI

[12] Linz, S. Bounding the Reticulation Number for Three Phylogenetic Trees, 2023 | DOI

[13] Mallet, J. Hybridization as an Invasion of the Genome, Trends in ecology & evolution, Volume 20 (2005) no. 5, pp. 229-237 | DOI

[14] Zhang, L. On Tree-Based Phylogenetic Networks, Journal of Computational Biology, Volume 23 (2016) no. 7, pp. 553-565 | DOI

Cited by Sources: