Ranking top-k trees in tree-based phylogenetic networks
From MaRDI portal
Publication:6317895
arXiv1904.12432MaRDI QIDQ6317895FDOQ6317895
Authors: Momoko Hayamizu, Kazuhisa Makino 
Publication date: 28 April 2019
Abstract: 'Tree-based' phylogenetic networks proposed by Francis and Steel have attracted much attention of theoretical biologists in the last few years. At the heart of the definitions of tree-based phylogenetic networks is the notion of 'support trees', about which there are numerous algorithmic problems that are important for evolutionary data analysis. Recently, Hayamizu (arXiv:1811.05849 [math.CO]) proved a structure theorem for tree-based phylogenetic networks and obtained linear-time and linear-delay algorithms for many basic problems on support trees, such as counting, optimisation, and enumeration. In the present paper, we consider the following fundamental problem in statistical data analysis: given a tree-based phylogenetic network whose arcs are associated with probability, create the top- support tree ranking for by their likelihood values. We provide a linear-delay (and hence optimal) algorithm for the problem and thus reveal the interesting property of tree-based phylogenetic networks that ranking top- support trees is as computationally easy as picking arbitrary support trees.
Statistical ranking and selection procedures (62F07) Problems related to evolution (92D15) Trees (05C05) Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms (68W40) Enumeration in graph theory (05C30)
This page was built for publication: Ranking top-k trees in tree-based phylogenetic networks
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6317895)
