Haplotype Inference on Pedigrees with Recombinations and Mutations

Haplotype Inference on Pedigrees with Recombinations and Mutations, Yuri Pirola, WABI 2010 (slides).

The work proposes a new combinatorial formulation for haplotype inference on general pedigrees that generalizes the existing combinatorial ones to a more realistic settings. We prove an approximation-preserving reduction from this problem, called Minimum Change Haplotype Configuration (MCHC), to a well-known coding theory problem, namely the Nearest Codeword Problem. This reduction automatically implies the approximability of MCHC within a factor O(n/log n) and, more importantly, it leads to a new very efficient heuristic algorithm that has been experimentally compared with other state-of-the-art HI methods. The software implementing the heuristic is freely available at this page under the GNU General Public License.