Journal Article

A better block partition and ligation strategy for individual haplotyping

Yuzhong Zhao, Yun Xu, Zhihao Wang, Hong Zhang and Guoliang Chen

in Bioinformatics

Volume 24, issue 23, pages 2720-2725
Published in print December 2008 | ISSN: 1367-4803
Published online October 2008 | e-ISSN: 1460-2059 | DOI:
A better block partition and ligation strategy for individual haplotyping

More Like This

Show all results sharing this subject:

  • Bioinformatics and Computational Biology


Show Summary Details


Motivation: Haplotype played an important role in the association studies of disease gene and drug responsivity over the past years, but the low throughput of 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 to estimate the frequencies of numerous possible haplotypes, the partition and ligation strategy was widely adopted to reduce the time complexity. The haplotypes were usually partitioned uniformly in the past, but recent studies showed that the haplotypes had their own block structure, which may be not uniform. More reasonable block partition and ligation strategy according to the haplotype structure may further improve the accuracy of individual haplotyping.

Results: In this article, we presented a simple algorithm for block partition and ligation, which provided better accuracy for individual haplotyping. The block partition and ligation could be completed within O(m2 logm+m2n) time complexity, where m represented the length of genotypes and n represented the number of individuals. We tested the performance of our algorithm on both real and simulated dataset. The result showed that our algorithm yielded better accuracy with short running time.

Availability: The software is publicly available at


Journal Article.  4682 words.  Illustrated.

Subjects: Bioinformatics and Computational Biology

Full text: subscription required

How to subscribe Recommend to my Librarian

Users without a subscription are not able to see the full content. Please, subscribe or login to access all content.