PedStr Software for Cutting Large Pedigrees for Haplotyping, IBD Computation and Multipoint Linkage Analysis

We propose an automatic heuristic algorithm for splitting large pedigrees into fragments of no more than a user-specified bit size. The algorithm specifically aims to split large pedigrees where many close relatives are genotyped and to produce a set of sub-pedigrees for haplotype reconstruction, IBD computation or multipoint linkage analysis with the help of the Lander-Green-Kruglyak algorithm. We demonstrate that a set of overlapping pedigree fragments constructed with the help of our algorithm allows fast and effective haplotype reconstruction and detection of an allele's parental origin. Moreover, we compared pedigree fragments constructed with the help of our algorithm and existing programs PedCut and Jenti for multipoint linkage analysis. Our algorithm demonstrated significantly higher linkage power than the algorithm of Jenti and significantly shorter running time than the algorithm of PedCut. The software package PedStr implementing our algorithms is available at http://mga.bionet.nsc.ru/soft/index.html.