Document Type
Article
Publication Date
8-2009
Abstract
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.
Recommended Citation
Holder, Allen and Langley, Thomas M., "A Decomposition of the Pure Parsimony Problem" (2009). Mathematical Sciences Technical Reports (MSTR). 15.
https://scholar.rose-hulman.edu/math_mstr/15
COinS
Comments
MSTR 09-02