Archives

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 […]

Pure Parsimony Xor Haplotyping, Yuri Pirola, ISBRA 2009 (slides). In this work we addressed the problem of haplotype inference from xor genotypes under the pure parsimony assumption. Exact algorithms for restricted instances, a fixed parameter algorithm, an approximation algorithm, and an effective heuristic have been proposed. A prototypical implementation of the heuristic is freely available […]

Minimum Factorization Agreement of Spliced ESTs, Yuri Pirola, WABI 2009 (slides). The work presents a new parsimony-based formulation for the problem of choosing the best alignment of an expressed sequence against a genomic sequence exploiting the redundancy of current expressed sequence databases. A preliminary experimental evaluation of the formulation and the related algorithm shows their […]