Novel and efficient tag SNPs selection algorithms

Issue title: Frontiers in Biomedical Engineering and Biotechnology – Proceedings of the 2nd International Conference on Biomedical Engineering and Biotechnology, 11–13 October 2013, Wuhan, China

Article type: Research Article

Authors: Chen, Wen-Pei^; | Hung, Che-Lun^; | Tsai, Suh-Jen Jane | Lin, Yaw-Ling^;

Affiliations: Department of Applied Chemistry, Providence University, Taiwan. E-mail: sjtsai@pu.edu.tw | Department of Computer Science and Communication Engineering, Providence University, Taiwan. E-mail: clhung@pu.edu.tw | Department of Computer Science and Information Engineering, Providence University, Taiwan. E-mail: yllin@pu.edu.tw

Note: [] Those authors contributed equally to this work.

Note: [] Those authors contributed equally to this work.

Note: [] Corresponding author. E-mail: yllin@pu.edu.tw. Department of Computer Science and Information Engineering, Providence University, 200, Sec. 7, Taiwan Boulevard, Taichung, Taiwan. Tel: +886-4-2632-8001 ext 18021; this work is supported in part by the National Science Council, Taiwan, R.O.C, grant NSC 99-2632-E-126-001-MY3 and NSC 100-2221-E-126-007-MY3.

Abstract: SNPs are the most abundant forms of genetic variations amongst species; the association studies between complex diseases and SNPs or haplotypes have received great attention. However, these studies are restricted by the cost of genotyping all SNPs; thus, it is necessary to find smaller subsets, or tag SNPs, representing the rest of the SNPs. In fact, the existing tag SNP selection algorithms are notoriously time-consuming. An efficient algorithm for tag SNP selection was presented, which was applied to analyze the HapMap YRI data. The experimental results show that the proposed algorithm can achieve better performance than the existing tag SNP selection algorithms; in most cases, this proposed algorithm is at least ten times faster than the existing methods. In many cases, when the redundant ratio of the block is high, the proposed algorithm can even be thousands times faster than the previously known methods. Tools and web services for haplotype block analysis integrated by hadoop MapReduce framework are also developed using the proposed algorithm as computation kernels.

Keywords: SNP, haplotype block, tag SNP selection, hadoop, non-redundant site, redundant ratio

DOI: 10.3233/BME-130942

Journal: Bio-Medical Materials and Engineering, vol. 24, no. 1, pp. 1383-1389, 2014