Design of Genetic Algorithm to enumerate multiple optimal solutions to haplotype assembly problem

doi:10.3778/j.issn.1002-8331.2010.11.003

Computer Engineering and Applications ›› 2010, Vol. 46 ›› Issue (11): 7-9.DOI: 10.3778/j.issn.1002-8331.2010.11.003

• 博士论坛 • Previous Articles Next Articles

Design of Genetic Algorithm to enumerate multiple optimal solutions to haplotype assembly problem

XIE Min-zhu¹，LIU Xin-qiu^2，3

1.College of Physics and Information Science，Hunan Normal University，Changsha 410081，China
2.College of Mathematics and Computer Science，Hunan Normal University，Changsha 410081，China
3.Department of Foundation Science，Hunan Engineering Vocational Technical College，Changsha 410151，China

Received:2009-12-31 Revised:2010-02-01 Online:2010-04-11 Published:2010-04-11
Contact: XIE Min-zhu

枚举单体型组装问题多个最优解的遗传算法设计

谢民主¹，刘新求^2，3

1.湖南师范大学物理信息与科学学院，长沙 410081
2.湖南师范大学数学与计算机科学学院，长沙 410081
3.湖南工程职业技术学院基础科学系，长沙 410151

通讯作者: 谢民主

Abstract

Abstract: The haplotype assembly problem aims to reconstruct a pair of haplotype of an individual from its DNA sequencing fragment data.There are some heuristic algorithms and parameterized algorithms for the various computational optimal models.However，these algorithms work out with only one optimal solution，i.e.a pair of haplotypes.However，the optimal solution to a biological problem is usually not unique，or the real solution may be suboptimal.The paper proposes a new genetic algorithm to enumerate multiple optimal solutions to the haplotype assembly problem.Experimental results show that this algorithm is more accurate in haplotype reconstruction and provides the chance for the biologists to choose one from these multiple solutions based on some biological knowledge.

Key words: Single-Nucleotide Polymorphisms（SNPs）, haplotype, heuristic algorithm, bioinformatics

摘要： 单体型组装问题就是根据个体基因组测序获得的DNA序列数据重构出该个体的一对单体型。目前单体型组装问题的各种优化计算模型已有相关的启发式算法和参数化精确算法，但是这些算法只能得出一个最优解，即一对单体型。可是生物问题的最优解往往不是唯一的，或者真实解可能只是接近最优的。该文设计了一个新的能枚举出最优的多个解的遗传算法。实验结果表明该算法具有较高的单体型重建精度，并为生物学家根据领域知识在算法获得的多个解的基础进一步选择提供了可能。

关键词: 单核苷酸多态性, 单体型, 启发式算法, 生物信息学

CLC Number:

TP301

XIE Min-zhu¹，LIU Xin-qiu^2，3. Design of Genetic Algorithm to enumerate multiple optimal solutions to haplotype assembly problem[J]. Computer Engineering and Applications, 2010, 46(11): 7-9.

谢民主¹，刘新求^2，3. 枚举单体型组装问题多个最优解的遗传算法设计[J]. 计算机工程与应用, 2010, 46(11): 7-9.

[1]	ZHANG Chengling, LI Jinjin, LIN Yidong. Attribute Reduction in Formal Contexts Based on OE-Concept Lattices [J]. Computer Engineering and Applications, 2021, 57(15): 82-89.
[2]	MENG Xin, YANG Qin, HAO Tingting, ZHANG Jie, CAO Cejun. Optimized Combination of Picking Path in Different Distributions and Algorithms [J]. Computer Engineering and Applications, 2020, 56(23): 229-236.
[3]	LI Yali, WANG Shuqin, CHEN Qianru, WANG Xiaogang. Comparative Study of Several New Swarm Intelligence Optimization Algorithms [J]. Computer Engineering and Applications, 2020, 56(22): 1-12.
[4]	YI Chengqi, GUO Xin, TONG Nannan, DOU Yue, CHEN Dong, WANG Jiandong. Innovation Situation Analysis Algorithm Based on Heuristic Model of Community Detection [J]. Computer Engineering and Applications, 2020, 56(15): 74-79.
[5]	HU Xiaomin, LIANG Tianyi, WANG Mingfeng, LI Min. Novel Tree Heuristic Search Algorithm for Robot Path Planning [J]. Computer Engineering and Applications, 2020, 56(11): 164-171.
[6]	CHI Zongzheng, DONG Shaozheng, GUO Tong, REN Zhilei, ZHOU Kuanjiu, GUO He. Research on Wind Farm Layout Based on Hyper-Heuristic [J]. Computer Engineering and Applications, 2019, 55(7): 220-225.
[7]	SHANG Zhengyang1, GU Jinan2, TANG Shixi2, SUN Xiaohong2. Efficient Residual-Space-Optimization Algorithm for Three Dimensional Container Loading Problem [J]. Computer Engineering and Applications, 2019, 55(5): 44-50.
[8]	ZHANG Jun, HE Ketai. Study on Hybrid Genetic and Simulated Annealing Algorithm for Three-Dimensional Packing Problems [J]. Computer Engineering and Applications, 2019, 55(14): 32-39.
[9]	WANG Changbao1, YANG Xibei1，2, DOU Huili1, CHEN Xiangjian1, WANG Pingxin3. Research on local attribute reduction approach via neighborhood decision error rate [J]. Computer Engineering and Applications, 2018, 54(6): 95-99.
[10]	WANG Zhuan, PEI Zeping. Order batching algorithm based on heuristic picking route for saving mileage [J]. Computer Engineering and Applications, 2018, 54(23): 203-209.
[11]	XU Xuesong1, XU Xinyao2. Simultaneous regression algorithm for multi-structure model fitting [J]. Computer Engineering and Applications, 2017, 53(6): 73-79.
[12]	WANG Yinglong1, HUA Jiajia1, QIAN Wenbin2, YANG Jun2. Dynamic algorithm of attribute reduction in set-valued decision information system [J]. Computer Engineering and Applications, 2017, 53(17): 60-64.
[13]	SONG Lijun, ZHAO Hu. Integrated order acceptance and scheduling for multi-node flow-line production [J]. Computer Engineering and Applications, 2015, 51(4): 249-253.
[14]	LI Lijuan, WU Xiao, WANG Zhilong. Research of no-idle flow shop scheduling based on improved bacteria foraging optimization algorithm [J]. Computer Engineering and Applications, 2015, 51(17): 255-258.
[15]	LE Meilong, ZHAO Yanying, LIU Xiuling. Shore-mounted gantry crane scheduling for single vessel under time window [J]. Computer Engineering and Applications, 2014, 50(9): 242-248.

Design of Genetic Algorithm to enumerate multiple optimal solutions to haplotype assembly problem

枚举单体型组装问题多个最优解的遗传算法设计

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics