TY - JOUR
T1 - Ranking Top-k Trees in Tree-Based Phylogenetic Networks
AU - Hayamizu, Momoko
AU - Makino, Kazuhisa
N1 - Funding Information:
The work of Momoko Hayamizu was supported in part by JST PRESTO under Grants JPMJPR16EB and JPMJPR1929. The work of Kazuhisa Makino was supported in part by JSPS KAKENHI under Grants 19K22841 and 20H05967.
Publisher Copyright:
© 2004-2012 IEEE.
PY - 2023/5/1
Y1 - 2023/5/1
N2 - Tree-based phylogenetic networks provide a powerful model for representing complex data or non-tree-like evolution. Such networks consist of an underlying evolutionary tree called a 'support tree' (also known as a 'subdivision tree') together with extra arcs added between the edges of that tree. However, a tree-based network can have exponentially many support trees, and this leads to a variety of computational problems. Recently, Hayamizu established a theory called the structure theorem for rooted binary phylogenetic networks and provided linear-time and linear-delay algorithms for different problems, such as counting, optimization, and enumeration of support trees. However, in practice, it is often more useful to search for both optimal and near-optimal solutions than to calculate only an optimal solution. In the present paper, we thus consider the following problem: Given a tree-based phylogenetic network N where each arc is weighted by its probability, compute the ranking of top-k support trees of N according to their likelihood values. We provide a linear-delay (and hence optimal) algorithm for this problem.
AB - Tree-based phylogenetic networks provide a powerful model for representing complex data or non-tree-like evolution. Such networks consist of an underlying evolutionary tree called a 'support tree' (also known as a 'subdivision tree') together with extra arcs added between the edges of that tree. However, a tree-based network can have exponentially many support trees, and this leads to a variety of computational problems. Recently, Hayamizu established a theory called the structure theorem for rooted binary phylogenetic networks and provided linear-time and linear-delay algorithms for different problems, such as counting, optimization, and enumeration of support trees. However, in practice, it is often more useful to search for both optimal and near-optimal solutions than to calculate only an optimal solution. In the present paper, we thus consider the following problem: Given a tree-based phylogenetic network N where each arc is weighted by its probability, compute the ranking of top-k support trees of N according to their likelihood values. We provide a linear-delay (and hence optimal) algorithm for this problem.
KW - Phylogenetic tree
KW - algorithm
KW - enumeration
KW - maximum likelihood estimation
KW - spanning tree
KW - subdivision tree
KW - support tree
KW - top-k ranking problem
KW - tree-based phylogenetic network
UR - http://www.scopus.com/inward/record.url?scp=85144813647&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85144813647&partnerID=8YFLogxK
U2 - 10.1109/TCBB.2022.3229827
DO - 10.1109/TCBB.2022.3229827
M3 - Article
C2 - 37015415
AN - SCOPUS:85144813647
SN - 1545-5963
VL - 20
SP - 2349
EP - 2355
JO - IEEE/ACM Transactions on Computational Biology and Bioinformatics
JF - IEEE/ACM Transactions on Computational Biology and Bioinformatics
IS - 3
ER -