When Three Trees Go to War
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 tha...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Peer Community In
2024-06-01
|
| Series: | Peer Community Journal |
| Online Access: | https://peercommunityjournal.org/articles/10.24072/pcjournal.419/ |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1825206388161249280 |
|---|---|
| author | van Iersel, Leo Jones, Mark Weller, Mathias |
| author_facet | van Iersel, Leo Jones, Mark Weller, Mathias |
| author_sort | van Iersel, Leo |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-3f1beb2deca4472e8bb5050a8078c78e |
| institution | Kabale University |
| issn | 2804-3871 |
| language | English |
| publishDate | 2024-06-01 |
| publisher | Peer Community In |
| record_format | Article |
| series | Peer Community Journal |
| spelling | doaj-art-3f1beb2deca4472e8bb5050a8078c78e2025-02-07T10:17:18ZengPeer Community InPeer Community Journal2804-38712024-06-01410.24072/pcjournal.41910.24072/pcjournal.419When Three Trees Go to War van Iersel, Leo0Jones, Mark1Weller, Mathias2https://orcid.org/0000-0002-9653-3690Delft Institute of Applied Mathematics, Mekelweg 4, 2628 CD, Delft // POSTBUS 5031, 2600 GA DelftDelft Institute of Applied Mathematics, Mekelweg 4, 2628 CD, Delft // POSTBUS 5031, 2600 GA DelftTechnical University of Berlin / Technische Universität Berlin, Straße des 17. Juni 135 10623 Berlin; 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 - FranceHow 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.https://peercommunityjournal.org/articles/10.24072/pcjournal.419/ |
| spellingShingle | van Iersel, Leo Jones, Mark Weller, Mathias When Three Trees Go to War Peer Community Journal |
| title | When Three Trees Go to War
|
| title_full | When Three Trees Go to War
|
| title_fullStr | When Three Trees Go to War
|
| title_full_unstemmed | When Three Trees Go to War
|
| title_short | When Three Trees Go to War
|
| title_sort | when three trees go to war |
| url | https://peercommunityjournal.org/articles/10.24072/pcjournal.419/ |
| work_keys_str_mv | AT vanierselleo whenthreetreesgotowar AT jonesmark whenthreetreesgotowar AT wellermathias whenthreetreesgotowar |