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

扫码查看

原文链接

万方数据
维普

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

外文标题：Research on Two-sided Genome Scaffold Filling Algorithm Based on Contig

作者：

柳楠、李胜华、朱永琦

展开 >

作者单位：

山东建筑大学计算机科学与技术学院,山东济南 250101

关键词：

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

基金：

国家自然科学基金山东省自然科学基金

项目编号：

61902221ZR2018MF012

出版年：

2022

DOI：

10.3969/j.issn.1673-629X.2022.12.032

计算机技术与发展

陕西省计算机学会

计算机技术与发展

CSTPCD

影响因子：0.621

ISSN：1673-629X

年,卷(期)：2022.32(12)

参考文献量5