A first step towards computing all hybridization networks for two rooted binary phylogenetic trees

2011/09/15 by Céline Scornavacca, Simone Linz, Scornavacca, Celine +3
Agricultural and Biological Sciences · Biochemistry, Genetics and Molecular Biology · #FOS: Biological sciences #Genetic diversity and population structure #Genomics and Phylogenetic Studies #Plant and animal studies #Populations and Evolution (q-bio.PE)

paper · pdf · doi:10.48550/arxiv.1109.3268

openalex publication_date 2011/09/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Recently, considerable effort has been put into developing fast algorithms to reconstruct a rooted phylogenetic network that explains two rooted phylogenetic trees and has a minimum number of hybridization vertices. With the standard approach to tackle this problem being combinatorial, the reconstructed network is rarely unique. From a biological point of view, it is therefore of importance to not only compute one network, but all possible networks. In this paper, we make a first step towards approaching this goal by presenting the first algorithm---called allMAAFs---that calculates all maximum-acyclic-agreement forests for two rooted binary phylogenetic trees on the same set of taxa.

Related

• Fast computation of all maximum acyclic agreement forests for two rooted binary phylogenetic trees
• Computing Hybridization Networks for Multiple Rooted Binary Phylogenetic Trees by Maximum Acyclic Agreement Forests
• Computing a Relevant Set of Nonbinary Maximum Acyclic Agreement Forests
• A 3-factor approximation algorithm for a Maximum Acyclic Agreement Forest on k rooted, binary phylogenetic trees
• Hybridization Number on Three Rooted Binary Trees is EPT