See the published version of this preprint at Algorithms for Molecular Biology.
This is a preprint, a preliminary version of a manuscript that has not completed peer review at a journal. Research Square does not conduct peer review prior to posting preprints. The posting of a preprint on this server should not be interpreted as an endorsement of its validity or suitability for dissemination as established information or for guiding clinical practice.
Learn more about In Review
A new preprint design is coming!
We have improved readability, clarity, accessibility, and opportunities for engagement.
Research Article
Lei Liu
Iowa State University College of Liberal Arts and Sciences
Corresponding Author
ORCiD: https://orcid.org/0000-0002-8566-6391
License:
This work is licensed under a CC BY 4.0 License. Read Full License
Background: A semi-labeled tree is a tree where all leaves as well as, possibly, some internal nodes are labeled
with taxa. Semi-labeled trees encompass ordinary phylogenetic trees and taxonomies. Suppose we are given a collection P = {T1, T2, . . . , Tk} of semi-labeled trees, called input trees, over partially overlapping sets of taxa. The agreement problem asks whether there exists a tree T , called an agreement tree, whose taxon set is the union of the taxon sets of the input trees such that the restriction of T to the taxon set of Ti is isomorphic to i, for each i ε 1, 2, . . . , k . The agreement problems is a special case of the supertree problem, the problem of synthesizing a collection of phylogenetic trees with partially overlapping taxon sets into a single supertree that represents the information in the input trees. An obstacle to building large phylogenetic supertrees is the limited amount of taxonomic overlap among the phylogenetic studies from which the input trees are obtained. Incorporating taxonomies into supertree analyses can alleviate this issue.
Results: We give a O(nk(i∈[k]di + log2(nk))) algorithm for the agreement problem, where n is the total number of distinct taxa in P, k is the number of trees in P, and di is the maximum number of children of a node in Ti. Our computational experience with the algorithm suggests that its performance in practice is much better than its worst-case bound indicates.
Keywords
Phylogenetic tree, Taxonomy, Agreement, Algorithm
Figure 1
Figure 2
Figure 3
Figure 4
Figure 5
Figure 6
Figure 7
Figure 8
Figure 9
Figure 10
The full text of this article is available to read as a PDF.
Loading...
Badges
Prescreen
This manuscript passed our Prescreen assessment
Complete author information
Appropriate declaration statements
Potential risks to human health
Prescreen
Peer Review Timeline
CURRENT STATUS: Published
View the published article at Algorithms for Molecular Biology.
Version 1
Posted 10 May, 2021
No community comments so far
Review #2 received
Received 03 Jun, 2021
Editorial decision: Minor revision
On 03 Jun, 2021
Review #1 received
Received 02 Jun, 2021
Reviewer #2 agreed
On 12 May, 2021
Reviews received
Received 10 May, 2021
Reviewer #1 agreed
On 10 May, 2021
Reviewers invited
Invitations sent on 05 May, 2021
Editor assigned
On 04 May, 2021
Submission checks complete
On 04 May, 2021
Editor invited
On 04 May, 2021
First submitted
On 21 Apr, 2021
Metrics
Comments: 0
PDF Downloads: ...
HTML Views: ...
Subject Areas
Molecular Biology
Learn more about our company.
A new preprint design is coming!
We have improved readability, clarity, accessibility, and opportunities for engagement.
See the published version of this preprint at Algorithms for Molecular Biology.
This is a preprint, a preliminary version of a manuscript that has not completed peer review at a journal. Research Square does not conduct peer review prior to posting preprints. The posting of a preprint on this server should not be interpreted as an endorsement of its validity or suitability for dissemination as established information or for guiding clinical practice.
Learn more about In Review
Research Article
Lei Liu
Iowa State University College of Liberal Arts and Sciences
Corresponding Author
ORCiD: https://orcid.org/0000-0002-8566-6391
Badges
Prescreen
This manuscript passed our Prescreen assessment
Complete author information
Appropriate declaration statements
Potential risks to human health
Prescreen
Peer Review Timeline
CURRENT STATUS: Published
View the published article at Algorithms for Molecular Biology.
Version 1
Posted 10 May, 2021
No community comments so far
Review #2 received
Received 03 Jun, 2021
Editorial decision: Minor revision
On 03 Jun, 2021
Review #1 received
Received 02 Jun, 2021
Reviewer #2 agreed
On 12 May, 2021
Reviews received
Received 10 May, 2021
Reviewer #1 agreed
On 10 May, 2021
Reviewers invited
Invitations sent on 05 May, 2021
Editor assigned
On 04 May, 2021
Submission checks complete
On 04 May, 2021
Editor invited
On 04 May, 2021
First submitted
On 21 Apr, 2021
Metrics
Comments: 0
PDF Downloads: ...
HTML Views: ...
Subject Areas
Molecular Biology
License:
This work is licensed under a CC BY 4.0 License. Read Full License
View the published article at Algorithms for Molecular Biology.
Background: A semi-labeled tree is a tree where all leaves as well as, possibly, some internal nodes are labeled
with taxa. Semi-labeled trees encompass ordinary phylogenetic trees and taxonomies. Suppose we are given a collection P = {T1, T2, . . . , Tk} of semi-labeled trees, called input trees, over partially overlapping sets of taxa. The agreement problem asks whether there exists a tree T , called an agreement tree, whose taxon set is the union of the taxon sets of the input trees such that the restriction of T to the taxon set of Ti is isomorphic to i, for each i ε 1, 2, . . . , k . The agreement problems is a special case of the supertree problem, the problem of synthesizing a collection of phylogenetic trees with partially overlapping taxon sets into a single supertree that represents the information in the input trees. An obstacle to building large phylogenetic supertrees is the limited amount of taxonomic overlap among the phylogenetic studies from which the input trees are obtained. Incorporating taxonomies into supertree analyses can alleviate this issue.
Results: We give a O(nk(i∈[k]di + log2(nk))) algorithm for the agreement problem, where n is the total number of distinct taxa in P, k is the number of trees in P, and di is the maximum number of children of a node in Ti. Our computational experience with the algorithm suggests that its performance in practice is much better than its worst-case bound indicates.
Figure 1
Figure 2
Figure 3
Figure 4
Figure 5
Figure 6
Figure 7
Figure 8
Figure 9
Figure 10
The full text of this article is available to read as a PDF.
Loading...