## Abstract

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.

Original language | English |
---|---|

Pages (from-to) | 2349-2355 |

Number of pages | 7 |

Journal | IEEE/ACM Transactions on Computational Biology and Bioinformatics |

Volume | 20 |

Issue number | 3 |

DOIs | |

Publication status | Published - 2023 May 1 |

## Keywords

- Phylogenetic tree
- algorithm
- enumeration
- maximum likelihood estimation
- spanning tree
- subdivision tree
- support tree
- top-k ranking problem
- tree-based phylogenetic network

## ASJC Scopus subject areas

- Biotechnology
- Genetics
- Applied Mathematics