tig序列。
f关键词：deBruij
图
贪婪图方法
启发式搜索
一、问题的重述
快速和准确的获取生物体的遗传信息对生命科学研究具有重要意义。随着测序技术的不断发展，新一代测序技术产生的在高通量、低成本的同时也带来了错误率略有则加、读长较短等缺点。本题要求利用数学模型，设计算法解决如下几个问题：（1）测序过程中可能出现的个别碱基对识别错误；（2）基因组中存在重复片段；（3）快速的处理海量的序列比对。
二、问题的分析
本题是基于新一代测序技术的基因组装算法问题，要求设计算法针对性的解决新一代测序技术带来的一些弊端。21read长度较短，数量较多debruij
图新一代测序技术所得的read长度较短，数量较多，不易发现read之间的重叠关系。可以将read转化成定长的kmer，然后寻找kmer之间的重叠关系。然后建立debruij
图，把短序列拼接问题转化为debruij
图中的欧拉路径问题。22个别碱基对识别错误多重对比纠错通过将多个read放在一起比对来发现错误，如图211所示。图中通过途中4条read比对，可发现read3中的一个碱基错误（read3的第五个碱基）
read1reda2read3
AACA
TGCATGCA
TGCTTGCTTGCT
TGACTGACCGAC
……ACAGACAG……CGTT……
f图21123基因组中存在大量重复片段重复片段可能导致拼接错误，或者导致不连续的较短co
tig出现。重叠片段类型主要有以下几种，如图231所示重复片段问题可以用如下问题解决：通过对比，可先将重复片段隔离开来，较高的覆盖度有利于重复片段的隔离，但是，较多的测序错误将不利于该过程的进行。如果重复片段比read长，可利用parede
dread来解决；如果重复片段比read短，那么该read又被称为spa
er，一个spa
er就是一个重复片段两端再加几个碱基组成。利用spa
er解决重复片段问题需要如下两个信息：一是重复片段两端配对的read，这两个read必须不相同；二是重复片段中的一个配对read，只要知道一个即可，另一个配对read可以不在重复片段中。通过分析已知的基因组，可获得有关重复片段的更多信息，如，重复片段的长度，重复片段的模式等。
原基因组：A拼接之后：A原基因组A拼接之后：B原基因组A拼接之后ABCBABCBARDACDRBRRCRRBRRBRA
图231
三、符号约定
f符号
定义利用现有的测序技术，可按一定的测序策略获得长度约为50100个碱基对的序列，称为读长；
read
co
tig（C）：superco
tig（S）：
由read经过一定算法拼接产生3kb～10Mb以内的一些基因组片段使用co
tig作为参考序列延伸r