A better block partition and ligation strategy for individual haplotyping

• DOI: 10.1093/bioinformatics/btn519
• Publication Date: 2008-10-10T00:34:47Z
• Authors: Yuzhong Zhao; Yun Xu; Zhihao Wang; Hong Zhang; Guoliang Chen
• Keywords: Genotype; Haplotypes; 0206 medical engineering; Humans; 02 engineering and technology; Polymorphism, Single Nucleotide; Algorithms; Linkage Disequilibrium

Abstract Motivation: Haplotype played an important role in the association studies of disease gene and drug responsivity over past years, but low throughput expensive biological experiments largely limited its application. Alternatively, some efficient statistical methods were developed to deduce haplotypes from genotypes directly. Because these algorithms usually needed estimate frequencies numerous possible haplotypes, partition ligation strategy was widely adopted reduce time complexity. The partitioned uniformly past, recent showed that had their own block structure, which may be not uniform. More reasonable according haplotype structure further improve accuracy individual haplotyping. Results: In this article, we presented a simple algorithm for ligation, provided better could completed within O(m2 logm+m2n) complexity, where m represented length n number individuals. We tested performance our on both real simulated dataset. result yielded with short running time. Availability: software is publicly available at http://mail.ustc.edu.cn/~zyzh. Contact: [e-mail]