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 -