2011/12/20 by Sebastian Böcker, Quang Bao Anh Bui, Böcker, Sebastian +7
Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #Computational Complexity (cs.CC) #Data Mining Algorithms and Applications #FOS: Computer and information sciences #Genome Rearrangement Algorithms #cs.CC
paper · pdf · doi:10.48550/arxiv.1112.4536
To be submitted
arxiv created 2011/12/20 · openalex publication_date 2011/12/20 · arxiv updated 2011/12/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Computing supertrees is a central problem in phylogenetics. The supertree method that is by far the most widely used today was introduced in 1992 and is called Matrix Representation with Parsimony analysis (MRP). Matrix Representation using Flipping (MRF), which was introduced in 2002, is an interesting variant of MRP: MRF is arguably more relevant that MRP and various efficient implementations of MRF have been presented. From a theoretical point of view, implementing MRF or MRP is solving NP-hard optimization problems. The aim of this paper is to study the approximability and the fixed-parameter tractability of the optimization problem corresponding to MRF, namely Minimum-Flip Supertree. We prove strongly negative results.