RECOMB 2003

Know about the book -

RECOMB 2003 is written by Webb Miller and published by . It's available with International Standard Book Number or ISBN identification 1581136358 (ISBN 10) and 9781581136357 (ISBN 13).

We study haplotype reconstruction under the Mendelian law of inheritance and the minimum recombination principleon pedigree data. We prove that the problem of finding a mini-mum-recombinant haplotype configuration (MRHC) is in general NP-hard. This is the first complexity result concerning the problem to our knowledge. An iterative algorithm based on blocks of consecutive resolved marker loci (called block-extension) is proposed. It is very efficient and can be used for large pedigrees with a large number of markers, especially for those data sets requiring few recombinants (or recombination events). A polynomial-time exact algorithm for haplotype reconstruction without recombinants is also presented. This algorithm first identifies all the necessary constraints based on the Mendelian law and the zero recombinant assumption, and represents them using a system of linear equations over the cyclic group Z2. By using a simple method based on Gaussian elimination, we could obtain all possible feasible haplotype configurations. We have tested the block-extension algorithm on simulated data generated on three pedigree structures. The results show that the algorithm performs very well on both multi-allelic and biallelic data, especially when the number of recombinants is small.