Efficient Haplotype Block Partitioning and Tag SNP Selection Algorithms under Various Constraints
Joint Authors
Hung, Che-Lun
Chen, Wen-Pei
Lin, Yaw-Ling
Source
Issue
Vol. 2013, Issue 2013 (31 Dec. 2013), pp.1-13, 13 p.
Publisher
Hindawi Publishing Corporation
Publication Date
2013-11-11
Country of Publication
Egypt
No. of Pages
13
Main Subjects
Abstract EN
Patterns of linkage disequilibrium plays a central role in genome-wide association studies aimed at identifying genetic variation responsible for common human diseases.
These patterns in human chromosomes show a block-like structure, and regions of high linkage disequilibrium are called haplotype blocks.
A small subset of SNPs, called tag SNPs, is sufficient to capture the haplotype patterns in each haplotype block.
Previously developed algorithms completely partition a haplotype sample into blocks while attempting to minimize the number of tag SNPs.
However, when resource limitations prevent genotyping all the tag SNPs, it is desirable to restrict their number.
We propose two dynamic programming algorithms, incorporating many diversity evaluation functions, for haplotype block partitioning using a limited number of tag SNPs.
We use the proposed algorithms to partition the chromosome 21 haplotype data.
When the sample is fully partitioned into blocks by our algorithms, the 2,266 blocks and 3,260 tag SNPs are fewer than those identified by previous studies.
We also demonstrate that our algorithms find the optimal solution by exploiting the nonmonotonic property of a common haplotype-evaluation function.
American Psychological Association (APA)
Chen, Wen-Pei& Hung, Che-Lun& Lin, Yaw-Ling. 2013. Efficient Haplotype Block Partitioning and Tag SNP Selection Algorithms under Various Constraints. BioMed Research International،Vol. 2013, no. 2013, pp.1-13.
https://search.emarefa.net/detail/BIM-1005572
Modern Language Association (MLA)
Chen, Wen-Pei…[et al.]. Efficient Haplotype Block Partitioning and Tag SNP Selection Algorithms under Various Constraints. BioMed Research International No. 2013 (2013), pp.1-13.
https://search.emarefa.net/detail/BIM-1005572
American Medical Association (AMA)
Chen, Wen-Pei& Hung, Che-Lun& Lin, Yaw-Ling. Efficient Haplotype Block Partitioning and Tag SNP Selection Algorithms under Various Constraints. BioMed Research International. 2013. Vol. 2013, no. 2013, pp.1-13.
https://search.emarefa.net/detail/BIM-1005572
Data Type
Journal Articles
Language
English
Notes
Includes bibliographical references
Record ID
BIM-1005572