應用免疫演算法於單核苷酸多型性多重標籤選擇之研究

Using Immune Algorithm for Multi-Marker Tagging SNP Selection Problem

王修培(Hsiu-Pei Wang)

指導教授 ： 陳大正

國立虎尾科技大學/管理學院/資訊管理研究所/碩士(2011年)

摘要

本研究主要在探討單核苷酸多型性多重標籤選擇問題（multi-marker tagging SNP selection problem），在過去的文獻中，對於最少的tagSNPs選擇問題，主要是注重在單核苷酸多型性單一標籤選擇（single-marker tagging SNP selection）的求解效率和tagSNP選擇方法，並未同時討論到單核苷酸多型性多重標籤選擇（multi-marker tagging SNP selection）的多重最佳解特性及解決方案。
依據過去相關文獻的研究，免疫演算法（immune algorithm, IA）廣泛的被使用來求解具有多重最佳解特性的問題。因此本研究以特徵選取的觀點提出免疫演算法來選擇出最少的SNPs集合也就是最少的tagSNPs集合來辨識全部的個體。
由實驗結果可知，對於不切割的資料本研究所提之免疫演算法僅需4個SNP所組成的tagSNP集合即可100%辨識出20筆Haplotype；對於切割成4135塊的資料本研究所提之免疫演算法僅需8036個SNP所組成的tagSNP集合即可100%辨識出4135塊中的每一塊20筆Haplotype；僅需4109個SNP所組成的tagSNP集合即可辨識出4135塊中每一塊80%的Haplotype。

關鍵字

免疫演算法 ； 單核苷酸多態性 ； 標籤單核苷酸多型性 ； 單核苷酸多型性多重標籤選擇

並列摘要

The purpose of this study is to investigate the multi-marker tagging Single Nucleotide Polymorphism (SNP) selection problem. The valuable information of human evolutionary history can be provided by SNPs, moreover, the genetic variants responsible for human diseases can also be identified by the extended studies of SNPs. However, molecular haplotype methods for SNPs are costly, laborious, and time consuming. Therefore, it’s needed to choose informative SNPs illustrated the primordial SNP distributions in the genome (tagSNP selection) for genome-wide association researches. Tagging SNPs (tagSNPs) are based on the human genome, and it can identify the human traits and the relationship of disease and gene. In literature, the studies of minimal tagged SNP selection problems were mostly focused on finding single-marker tagged set, but the issue of multi-marker tagged set has not been investigated in the past. Because of the problem of minimizing the number of representative SNPs within a block to uniquely distinguish all of the haplotypes belongs to the minimum test set problem, which has been proven to be NP-Complete, so that the heuristic methods become more popular approaches. In this research, an immune algorithm based approach has been proposed for solving the minimum tagSNPs set which is able to differentiate all individuals. Numerical examples indicate that the proposed immune based approach performs better than the other approaches in literature for SNP selection problems considered in this study. Finally, based upon the findings, some implications are proposed for further research.

並列關鍵字

Immune algorithm ； SNP ； TagSNP ； Multi-marker tagging SNP selection

參考文獻

52. 江泰緯，2008，「以網格運算為基礎之進化式演算法於資料探勘分類反應模型建立之研究」，國立虎尾科技大學資訊管理系碩士論文。

59. 曹惠鈴，2007，「運用混合式進化演算法於法則探勘之回應模型」，國立虎尾科技大學資訊管理系碩士論文。

2. Avi-Itzhak, H., Su X., et al., 2003, “Selection of minimum subsets of single nucleotide polymorphisms to capture haplotype block diversity”, Pacific Symposium on Biocomputing, 8, pp.466-477.

3. Bader, J.S., 2001, “The relative power of SNPs and haplotype as genetic markers for association tests”, Pharmacogenomics, 2(1), pp.11-24.

4. Bafna, V., Gusfield, D., Lancia, G., and Yooseph, S., 2003, “Haplotyping as a perfect phylogeny: a direct approach”, Journal of Computational Biology, 10(3-4), pp.323–340.