Related Experiment Video
Updated: Jul 19, 2026

A Concoction Pipeline for Generating Molecular Operational Taxonomic Units (MOTUs) Among Riparian and Aquatic Beetles
Published on: July 11, 2025
Islands of tractability for parsimony haplotyping
Roded Sharan1, Bjarni V Halldórsson, Sorin Istrail
1School of Computer Science, Tel-Aviv University, Tel-Aviv, Israel. roded@tau.ac.il
Abstract:
We study the parsimony approach to haplotype inference, which calls for finding a set of haplotypes of minimum cardinality that explains an input set of genotypes. We prove that the problem is APX-hard even in very restricted cases. On the positive side, we identify islands of tractability for the problem, by focusing on instances with specific structure of haplotype sharing among the input genotypes. We exploit the structure of those instance to give polynomial and constant-approximation algorithms to the problem. We also show that the general parsimony haplotyping problem is fixed parameter tractable.
Related Concept Videos
Hardy-Weinberg Principle
Phylogenetic Trees
Single Nucleotide Polymorphisms-SNPs
Evolutionary Relationships through Genome Comparisons
Multiple Allele Traits
Multiple Allele Traits

