![]() |
Home | Issues | About JGAA | Instructions for Authors |
DOI: 10.7155/jgaa.00633
Computing consensus networks for collections of 1-nested phylogenetic networks
Vol. 27, no. 7, pp. 541-563, 2023. Regular paper.
Abstract An important and well-studied problem in phylogenetics
is to compute a consensus tree so as to summarize the common features within
a collection of rooted phylogenetic trees, all whose leaf-sets are bijectively labeled by the
same set \(X\) of species.
More recently, however, it has become of interest to find a consensus
for a collection of more general, rooted directed acyclic graphs all of whose
sink-sets are bijectively labeled by \(X\), so called
rooted phylogenetic networks.
These networks are used to analyze the evolution of
species that cross with one another,
such as plants and viruses. In this paper, we introduce
an algorithm for computing a consensus for a collection of
so-called 1-nested phylogenetic networks.
Our approach builds on a previous result by Roselló et al.
that describes an encoding for any 1-nested phylogenetic network
in terms of a collection of ordered pairs of subsets of \(X\).
More specifically, we characterize those collections of ordered pairs that
arise as the encoding of some 1-nested phylogenetic network, and then use this
characterization to
compute a consensus network
for a collection of $t \geq 1$ 1-nested networks in $O(t|X|^2+|X|^3)$ time.
Applying our algorithm to a collection of phylogenetic trees
yields the well-known majority rule consensus tree.
Our approach leads to several new directions for future work, and we
expect that it should provide a useful new tool to
help understand complex evolutionary scenarios.
![]() |
Submitted: July 2021.
Reviewed: September 2022.
Revised: November 2022.
Accepted: July 2023.
Final: July 2023.
Published: August 2023.
Communicated by
Fabio Vandin
|
Journal Supporters
|