基于枚举策略的三倍体个体单体型重建算法

摘要：

求解三倍体个体单体型对于探索三倍体物种的遗传特性和表型差异等方面的研究具有重要的推动作用.针对带基因型信息的最少错误更正(MEC/GI)模型,提出了一种基于枚举策略的三倍体个体单体型重建算法EHTR.该算法依次重建3条单体型上的每一个单核苷酸多态性位点取值,对于给定位点,首先根据其基因型取值枚举该位点的3种单体型取值情况,然后选择片段支持度最高的取值作为该位点的重建值,算法的总时间复杂度为O(mn+mlogm+ cnl).采用CELSIM和MetaSim两种测序片段模拟生成器生成实验测试数据,在片段覆盖率、错误率、单片段长度、单体型长度和单体型海明距离等参数的不同设置下,对算法EHTR,GTIHR,W-GA和Q-PSO的重建率和运行时间进行对比分析.实验结果显示,算法EHTR在不同的参数设置下均能以更短的运行时间获得更高的重建率.

关键词：序列分析、三倍体、单体型、基因型、最少错误更正、枚举

所属期刊栏目：44

分类号：TP301(计算技术、计算机技术)

资助基金：国家自然科学基金项目61363035,61502111;广西自然科学基金项目2015GXNSFAA139288,2013GXNSFBA019263,2012GXNSFAA053219;“八桂学者”工程专项,广西多源信息挖掘与安全重点实验室系统性研究基金项目14-A-03-02,15-A-03-02

在线出版日期：2017-04-10（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：75-79,112