遗传算法和单体型组装加权最小字符翻转问题

doi:10.3778/j.issn.1002-8331.2010.08.063

计算机工程与应用 ›› 2010, Vol. 46 ›› Issue (8): 217-220.DOI: 10.3778/j.issn.1002-8331.2010.08.063

遗传算法和单体型组装加权最小字符翻转问题

姚雄武，郑金华，李晶，文诗华

湘潭大学信息工程学院，湖南湘潭 411105

收稿日期:2008-09-09 修回日期:2008-11-21 出版日期:2010-03-11 发布日期:2010-03-11
通讯作者: 姚雄武

Genetic algorithm and haplotype assembly problem Weighted Minimum Letter Flips

YAO Xiong-wu，ZHENG Jin-hua，LI Jing，WEN Shi-hua

School of Information Engineering，Xiangtan University，Xiangtan，Hunan 411105，China

Received:2008-09-09 Revised:2008-11-21 Online:2010-03-11 Published:2010-03-11
Contact: YAO Xiong-wu

摘要/Abstract

摘要： 单体型组装加权最小字符翻转（WMLF）问题指定个体联配的加权DNA片断数据，翻转权值和最小的SNP位点以推测出该个体的一对单体型。该问题是NP-难的，至今尚无实用的搜索寻优算法。根据DNA测序片段数据的特点提出了一种遗传算法。对于实际的生物实验数据，即使数据很大，该算法也可以在较短的时间得到WMLF问题的满意解，具有良好的可扩展性和较高的实用价值。

Abstract: Given a set of weighted aligned DNA fragments of an individual，the haplotype assembly problem Weighted Minimum Letter Flips（WMLF） is to infer a pair of haplotypes of the individual by flipping some SNPs with the sum of weights of the flipped SNPs minimized.WMLF is NP-hard，and there is no practical algorithm to search optimal solution for the problem.Based on the characters of DNA fragments，this paper introduces a genetic algorithm.For the practical fragment data，the algorithm can solve the WMLF problem efficiently even if the data are larger，and it is scalable and applicable in practice.

中图分类号:

TP18

姚雄武，郑金华，李晶，文诗华. 遗传算法和单体型组装加权最小字符翻转问题[J]. 计算机工程与应用, 2010, 46(8): 217-220.

YAO Xiong-wu，ZHENG Jin-hua，LI Jing，WEN Shi-hua. Genetic algorithm and haplotype assembly problem Weighted Minimum Letter Flips[J]. Computer Engineering and Applications, 2010, 46(8): 217-220.

[1]	闫林，张新明，何健仓，李富有. 粗糙集、商空间及概念格中粒的统一描述[J]. 计算机工程与应用, 2010, 46(9): 38-41.
[2]	汪红林^1，2，王红玲^1，2，周国栋^1，2. 语义分析中谓词标识的特征工程[J]. 计算机工程与应用, 2010, 46(9): 134-137.
[3]	张锐^1，2，张涛³，高辉⁴. RQEA-SVR在交通流预测中的应用[J]. 计算机工程与应用, 2010, 46(9): 241-245.
[4]	郝武伟¹，曾建潮². 基于聚类分析的随机微粒群算法[J]. 计算机工程与应用, 2010, 46(8): 40-44.
[5]	李朝鹏^1，2，成运¹，李肯立²，周旭³. 哈密尔顿回路问题的DNA表面计算模型[J]. 计算机工程与应用, 2010, 46(8): 48-51.
[6]	陈学松，杨宜民. 基于递推最小二乘法的多步时序差分学习算法[J]. 计算机工程与应用, 2010, 46(8): 52-55.
[7]	戴宏亮^1，2. 小波支持向量回归在瓦斯涌出量预测中的应用[J]. 计算机工程与应用, 2010, 46(7): 15-17.
[8]	马建敏¹，朱朝晖²，张文修³. 相容关系下集值信息系统的粗糙熵[J]. 计算机工程与应用, 2010, 46(7): 29-31.
[9]	王加阳¹，杜库¹，胡沛¹，高灿². 基于非对称相似差别矩阵知识约简[J]. 计算机工程与应用, 2010, 46(7): 44-45.
[10]	朱庆生，钟洵，杨鹏. NJW在离群数据挖掘中的应用研究[J]. 计算机工程与应用, 2010, 46(7): 128-130.
[11]	唐少先. 数据挖掘中粗糙集边界的处理方法[J]. 计算机工程与应用, 2010, 46(7): 131-133.
[12]	徐红升，张瑞玲. ART与概念相似在电子商务推荐系统中的应用[J]. 计算机工程与应用, 2010, 46(7): 213-217.
[13]	焦尚彬，刘丁. 博弈树置换表启发式算法研究[J]. 计算机工程与应用, 2010, 46(6): 42-45.
[14]	田生文，王伊蕾，李阿丽. 一种应用复杂网络特征的K-means初始化方法[J]. 计算机工程与应用, 2010, 46(6): 127-129.
[15]	黄信¹，陶华¹，钟卫军². 基于混合粒子群算法的二维导体柱目标识别[J]. 计算机工程与应用, 2010, 46(6): 201-203.

遗传算法和单体型组装加权最小字符翻转问题

Genetic algorithm and haplotype assembly problem Weighted Minimum Letter Flips

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics