基于片段重叠群的基因组片段填充问题研究

Scaffold filling technology in the field of genome comparison can improve the accuracy and completeness of genome sequence gotten by biological sequencing and assembling, and has good practical value. In this project, missing genes are inserted between contigs to make resulting sequences as similar as possible by computing genomic distance for one-sided/two-sided permutation/sequence filling. With repetitive genes, the local search technique will be used to design less-than-2-approximate algorithms. A polynomial time algorithm will be realized in two-sided permutation filling. The project intends to develop an experimental platform to verify the validity of algorithms using standard gene bank data. The project mainly focuses on the study of the problem of scaffold filling based on contigs, which is a more general form of the scaffold filling problem in the previous study. The question's input is more practical sequences constructed by contigs instead of general sequences. Missing genes' insertion location is no longer between any two genes, but is limited to between two contigs so as to ensure that the contig structure is not damaged by the inserted genes. This problem is more challenging and practical because previous problem is a special example of this one.

基因组比较领域中的片段填充技术能够提高生物测序、拼接后基因组序列的准确性和完整性，具有一定的应用价值。本项目将针对包含和不包含重复基因的单、双面片段重叠群填充问题，通过计算基因组距离，将缺失基因插入不完备的片段重叠群序列中，使最终获得的基因组序列尽可能相似。针对包含重复基因的情况，项目拟利用局部搜索等技术设计并实现近似比在2以内的近似算法，而对于不含重复基因的双面填充问题，设计多项式时间算法。项目拟设计并开发实验平台，利用标准基因库数据，验证算法的有效性。基于片段重叠群的基因组片段填充问题，是前期普通基因组片段填充问题的更一般形式。问题的输入从普通基因组片段序列变为实际应用中更常用的片段重叠群序列。缺失基因的插入位置也不再是任意两个基因之间，而被限制在片段重叠群之间，从而保证已获有意义的基因结构不被插入的基因破坏。相比可视为特例的前期研究，项目更具挑战性和实用性。

项目主要进行基于片段重叠群的最大化邻接距离的单面和双面片段填充问题的研究，该问题是前期研究的普通基因组片段填充问题的更一般形式。而前期研究的问题，缺失基因可以插入任意两个基因之间，而在本项目中插入位置受到限制，研究的问题复杂性更高。利用片段填充算法能够提高生物测序、拼接后基因组序列的准确性和完整性，具有一定的应用价值。. 该项目主要研究内容是针对输入基因序列由片段重叠群构成，缺失基因的插入位置被限制在片段填充群之间的基因组片段填充的问题，主要包括两方面的重点研究内容：一是基于片段重叠群的不包含重复基因的双面片段重叠群基因组片段填充问题的多项式时间算法；二是基于片段重叠群的包含重复基因的单面片段重叠群基因组片段填充问题的近似算法。. 在不包含重复基因的双面片段重叠群基因组片段填充问题中，首先通过分析邻接匹配的唯一性，针对一部分特殊实例，利用最大匹配思想实现该类实例的O(n2)多项式时间算法的设计、时间复杂度分析和算法正确性证明。其次，扩大实例范围到一般实例，将前期特殊实例的处理过程作为一般实例处理初期剪枝的过程，使用加权带花树算法实现Type-2和Type-3的同时处理，完成O(n4)多项式时间算法的设计和实现，实现算法的可视化程序。程序能够实现问题实例的随机生成、算法执行过程演示，形象的展示了算法的实现过程，验证每个实例的正确性。在包含重复基因的单面片段重叠群基因组片段填充问题中，在插入1-Type-1的2-近似算法的基础上，引入2-Type-1和3-Type-1的插入，利用最大匹配和局部优化，设计了一个近似算法，将近似比提高到15/8；在包含重复基因的双面片段重叠群基因组片段填充问题中，设计了一个2-近似算法，通过程序验证了两个算法的有效性。. 项目执行期间，共发表8篇论文，其中SCI检索论文2篇，EI检索论文3篇，CCF推荐C类中文期刊3篇，撰写《基因组片段填充算法》专著1部，获得3项相关软件著作权，申请专利2项，已进入实质审查阶段。. 综上，项目在执行期内，取得了一定的研究成果，特此申请结题，请予以批准。

内容获取失败，请点击重试