Digital Commons Network^™

A Decomposition Of The Pure Parsimony Problem, Allen Holder, Thomas M. Langley

Mathematical Sciences Technical Reports (MSTR)

We partially order a collection of genotypes so that we can represent the problem of inferring the least number of haplotypes in terms of substructures we call g-lattices. This representation allows us to prove that if the genotypes partition into chains with certain structure, then the NP-Hard problem can be solved efficiently. Even without the specified structure, the decomposition shows how to separate the underlying integer programming model into smaller models.