Journal
IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS
Volume 20, Issue 3, Pages 2349-2355Publisher
IEEE COMPUTER SOC
DOI: 10.1109/TCBB.2022.3229827
Keywords
Phylogenetic tree; tree-based phylogenetic network; support tree; subdivision tree; spanning tree; top-k ranking problem; maximum likelihood estimation; enumeration; algorithm
Ask authors/readers for more resources
Tree-based phylogenetic networks are a powerful model for representing complex data or non-tree-like evolution. However, these networks can have exponentially many support trees, leading to various computational problems. Hayamizu recently proposed a structure theorem and provided linear-time and linear-delay algorithms for different problems. In this paper, we focus on ranking the top-k support trees of a tree-based phylogenetic network based on their likelihood values, and present a linear-delay (optimal) algorithm for this problem.
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available