标签SNPs选择及重构算法研究

计算机工程与科学

标签SNPs选择及重构算法研究

赵婧1,魏彬2

（1.西京学院控制工程学院,陕西西安 710123;2.武警工程大学电子技术系,陕西西安 710086）

收稿日期:2015-09-18 修回日期:2015-10-27 出版日期:2016-11-25 发布日期:2016-11-25
基金资助:
陕西省教育厅科研计划（15JK2187）;西京学院科研基金（XJ140115）;武警工程大学基础研

究基金（WJY201518）

A tag SNPs selection and reconstruction algorithm

ZHAO Jing1,WEI Bin2

（1.School of Control Engineering,Xijing University,Xi’an 710123;

2.Department of Electronic Technique,Armed Police Engineering University,Xi’an

710086,China）

Received:2015-09-18 Revised:2015-10-27 Online:2016-11-25 Published:2016-11-25

摘要/Abstract

摘要：

研究复杂疾病与SNP之间的相关性是生物信息学最为重要的任务之一，然而基因分型的巨大花费却限制了

其发展及应用。因此，选择部分有代表性的SNP（即标签SNP选择问题）进行研究，从而降低研究所需费

用就显得十分必要。近年来，已有一些算法被提出用于解决该问题，但是大多数方法在预测精度及标签

选择数目等指标方面仍未能达到实际应用的需求。据此，设计了一种前向矩阵法用于标签SNP的选择，并

用改进的PSO算法对非标签SNP进行预测。最后通过大量数据集上的实验表明了算法与常用方法相比可选

择更少的标签，同时可获得更高的预测精度，即在性能方面有了明显的提升，更适合于标签SNP选择问题

的研究。

关键词: 单核苷酸多态性, 标签, 粒子群算法

Abstract:

Obtaining the association between complex diseases and single nucleotide polymorphisms

(SNPs) is one of the most important tasks of bioinformatics.However,the huge spending

limits its development and applications,selecting a set of tag SNPs therefore becomes an

important step to reduce the cost for association study.Recently,some algorithms have been

proposed for solving this problem,but most of them cannot meet the requirements of

practical applications in terms of accuracy level and number of tags.We introduce a new

method which uses an improved particle swarm optimization algorithm to predict the nontag

SNPs,and employ an novel forwardmatrix method to select tag SNPs.To measure the quality

of the correction rate and the number of tag SNPs,we utilize several databases to test our

method,and we also compare it with other methods.The results show that the proposed method

can effectively enhance the tag SNPs prediction in terms of accuracy and a smaller subset

of tag SNPs.

Key words: single nucleotide polymorphism, tag, particle swarm optimization

赵婧1,魏彬2. 标签SNPs选择及重构算法研究[J]. 计算机工程与科学.

ZHAO Jing1,WEI Bin2.

A tag SNPs selection and reconstruction algorithm

[J]. Computer Engineering & Science.

参考文献

［1］Liao B,Li X,Zhu W,et al.Multiple ant colony algorithm method for selecting tag SNPs［J

］.Journal of Biomedical Informatics,2012,45(5):931937.

［2］Zhang L,Kim S.Learning gene networks under SNP perturbations using eQTL datasets

［J］.PLoS Computational Biology,2014,10(2):247259.

［3］Wu C,Cui Y.Boosting signals in genebased association studies via efficient SNP

selection［J］.Briefings in Bioinformatics,2014,15(2):279291.

［4］Johnson G C,Esposito L,Barratt B J,et al.Haplotype tagging for the identification of

common disease genes［J］.Nature Genetics,2001,29(2):233237.

［5］Patil N,Berno A J,Hinds D A,et al.Blocks of limited haplotype diversity revealed by

highresolution scanning of human chromosome 21［J］.Science,2001,294(5547):17191723.

［6］Anderson E C,Novembre J.Finding haplotype block boundaries by using the minimum

descriptionlength principle［J］.American Journal of Human Genetics,2003,73(2):336354.

［7］Koivisto M,Kivioja T,Maqnnila H,et al.Hidden Markov modelling techniques for haplotype

analysis［C］∥Proc of the 15th International Conference on Algorithmic Learning Theory,

2004:3752.

［8］Chang C J,Huang Y T,Chao K M.A greedier approach for finding tag SNPs

［J］.Bioinformatics,2006,22(6):685691.

［9］Phuong T M,Lin Z,Altman R B.Choosing SNPs using feature selection［J］.Journal of

Bioinformatics and Computational Biology,2006,4(2):241257.

［10］He J,Westbrooks K,Zelikovsky A.Linear reduction method for predictive and informative

tag SNP selection［J］.International Journal of Bioinformatics Research and

Applications,2005,1(3):24960.

［11］Ilhan I a G T.How to select tag SNPs in genetic association studies?The CLONTagger

method with parameter optimization［J］.Omicsa Journal of Integrative Biology,2013,17

(7):368383.

［12］Ilhan I a G T.A genetic algorithmsupport vector machine method with parameter

optimization for selecting the tag SNPs［J］.Journal of Biomedical Informatics,2013,46

(2):328340.

［13］Chuang L Y,Huang W L,Yang CH.Chaos embedded particle swarm optimization for tag

single nucleotide polymorphism selection［C］∥Proc of the IEEE 26th International

Conference on Advanced Information Networking and Applications,2012:283288.

［14］Li M,Cao Z,Li X,et al.A novel informative SNPs selection method based on genetic

algorithm［J］.Journal of Computational and Theoretical Nanoscience,2014,11(10):21092114.

［15］Wei Bin,Chen Xiao,Zhao Jing.An improved particle swarm optimization based on wolves’

activities circle［C］∥Proc of the 10th World Congress on Intelligent Control and

Automation,2012:7.

［16］Ding K,Kullo I J.Methods for the selection of tagging SNPs:A comparison of tagging

efficiency and performance［J］.European Journal of Human Genetics,2007,15(2):228236.

［17］Lin Z,Russ B A.Finding haplotype tagging SNPs by use of principal components analysis

［J］.American Journal of Human Genetics,2004,75(5):850861.

［18］Nothnagel M,Furst R,Rohde K.Entropy as a measure for linkage disequilibrium over

multilocus haplotype blocks［J］.Human Heredity,2002,54(4):186198.

［19］Weale M E.Selection and evaluation of tagging SNPs in the neuronalsodiumchannel

gene SCN1A:Implications for linkagedisequilibrium gene mapping［J］.American Journal of

Human Genetics,2003,73(3):551565.

［20］Carlson C S,Eberle M A,Rieder M J,et al.Selecting a maximally informative set of

singlenucleotide polymorphisms for association analyses using linkage disequilibrium［J］

.American Journal of Human Genetics,2004,74(1):106120.

［21］Chen W P,Hung C L,Tsai S J,et al.Novel and efficient tag SNPs selection algorithms［J

］.BioMedical Materials and Engineering,2014,24(1):13831389.

［22］Goktepe I I.A genetic algorithmsupport vector machine method for selecting tag

single nucleotide polymorphisms［J］.International Journal of Innovative

Computing,Information & Control,2013,9(2):525541.

［23］Wang J,Guo M Z,Wang C Y.CGTS:A siteclustering graph based tagSNP selection

algorithm in genotype data［J］.BMC Bioinformatics,2009,10(suppl):111.

[1]	蔡雨岐, 郭卫斌. 基于多级语义信息融合编码的序列标注方法[J]. 计算机工程与科学, 2022, 44(12): 2266-2272.
[2]	庞兴龙, 朱国胜, 杨少龙, 李修远. 一种基于聚类与噪声的网络流量分类方法[J]. 计算机工程与科学, 2022, 44(07): 1207-1215.
[3]	甘秋云. ED算法和SNP-index算法计算SNP位点的比较分析——以拟南芥为例[J]. 计算机工程与科学, 2022, 44(04): 707-712.
[4]	皇甫斐斐, 杨阳, 邓晓懿, . 基于节点影响力的理性节点标签传播算法[J]. 计算机工程与科学, 2022, 44(04): 713-722.
[5]	严春满, 张昱瑶, 张迪. 改进标签一致KSVD字典学习的人脸识别算法[J]. 计算机工程与科学, 2022, 44(02): 291-297.
[6]	李雨晨, 魏巍, 白伟明, 王达. 基于标签共现关系的多标签特征选择[J]. 计算机工程与科学, 2021, 43(11): 2049-2055.
[7]	陈海龙, 闫五岳, 孙海娇, 程苗. 标签扩展的协同过滤推荐算法[J]. 计算机工程与科学, 2021, 43(10): 1826-1832.
[8]	程玉胜, 曹天成, 王一宾, 郑伟杰. 基于负相关性增强的不平衡多标签学习算法[J]. 计算机工程与科学, 2021, 43(09): 1700-1710.
[9]	王鑫, 廖祎玮, 赵国生, 王健, 谢宝文. 一种面向任务需求的群智感知任务分配模型[J]. 计算机工程与科学, 2021, 43(08): 1512-1520.
[10]	李晓红, 王闪闪, 马堉银, 马慧芳. 融合相似度图和随机游走模型的多标签短文本分类算法[J]. 计算机工程与科学, 2021, 43(06): 1081-1087.
[11]	陈文祺, 王英, 王鑫, 汪洪吉. 基于生成对抗网络的多标签节点分类研究[J]. 计算机工程与科学, 2021, 43(02): 280-287.
[12]	王翼虎, 王思明. 基于改进粒子群算法的无人机路径规划[J]. 计算机工程与科学, 2020, 42(09): 1690-1696.
[13]	潘曙灿, 许青林. 融合特征向量中心性与标签熵的标签传播算法[J]. 计算机工程与科学, 2020, 42(08): 1489-1499.
[14]	王永琦, 江潇潇. 基于混合灰狼算法的机器人路径规划[J]. 计算机工程与科学, 2020, 42(07): 1294-1301.
[15]	杨岚雁, 靳敏, 张迎春, 张珣. 一种基于关联规则的MLKNN多标签分类算法[J]. 计算机工程与科学, 2020, 42(07): 1309-1317.