基于Contig的双面基因组片段填充算法研究

摘要：

随着生物测序技术的快速发展,人们能够在更短的时间内获得大规模的基因片段序列,如何对不完整的基因组片段进行填充使其变得完整已经被越来越多的人关注.基于普通序列的双面基因组问题是将缺失基因X填充到一个不完整基因组片段A中,得到A',将缺失基因Y填充到一个不完整基因组片段B中,得到B',使得A'和B'之间的邻接数最大化.测序获得的基因组片段通常由片段重叠群(contig)组成,缺失基因只能插入到contig两端.该算法针对基因组片段重叠群一类实例,首先为了简化基因组片段,进行合并符合条件的连续缺失串操作,其后进行具有一一对应关系的type-2类型缺失串的插入操作;其次采用贪婪搜索策略对type-1类型缺失串进行插入操作,然后对type-3串进行插入操作.设计了多项式时间算法,证明了算法的正确性,分析了算法的时间复杂度,开发了算法测试平台,进一步验证了算法的有效性.

关键词：基因组、多项式时间、贪婪搜索、片段重叠群、算法测试、邻接

所属期刊栏目：32

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

资助基金：国家自然科学基金;山东省自然科学基金项目

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

页数：共8页

页码：213-220