SNPs Selection using Gravitational Search Algorithm and Exhaustive Search for Association Mapping

Workshop and International Seminar on Science of Complex Natural Systems

Kusuma, W.A.^1 ; Hasibuan, L.S.^1 ; Istiadi, M.A.^1

Department of Computer Science, Bogor Agricultural University, Kampus IPB, Indonesia Jalan Meranti Wing 20, West Java, Bogor, Indonesia^1

关键词: Association mapping;    Combinatorial problem;    Computation time;    Computer resources;    Gravitational search algorithm (GSA);    Gravitational search algorithms;    Heuristic search;    Single nucleotide polymorphisms;   

Others  :  https://iopscience.iop.org/article/10.1088/1755-1315/31/1/012015/pdf
DOI  :  10.1088/1755-1315/31/1/012015

来源: IOP

【 摘 要 】

Single Nucleotide Polymorphisms (SNPs) are known having association to phenotipic variations. The study of linking SNPs to interest phenotype is refer to Association Mapping (AM), which is classified as a combinatorial problem. Exhaustive Search (ES) approach is able to be implemented to select targeted SNPs exactly since it evaluate all possible combinations of SNPs, but it is not efficient in terms of computer resources and computation time. Heuristic Search (HS) approach is an alternative to improve the performance of ES in those terms, but it still suffers high false positive SNPs in each combinations. Gravitational Search Algorithm (GSA) is a new HS algorithm that yields better performance than other nature inspired HS. This paper proposed a new method which combined GSA and ES to identify the most appropriate combination of SNPs linked to interest phenotype. Testing was conducted using dataset without epistasis and dataset with epistasis. Using dataset without epistasis with 7 targeted SNPs, the proposed method identified 7 SNPs - 6 True Positive (TP) SNPs and 1 False Positive (FP) SNP- with association value of 0.83. In addition, the proposed method could identified 3 SNPs- 2 TP SNP and 1 FP SNP with association value of 0.87 by using dataset with epistases and 5 targeted SNPs. The results showed that the method is robust in reducing redundant SNPs and identifying main markers.