卢志远 谢建明 孙 啸

(东南大学生物电子学国家重点实验室，南京 210096)

在过去的5年中，基因组测序技术取得了长足的进展.以大规模并行测序平台为基础的第二代测序技术大量涌现，其特点就是测序得到的片段数量巨大且长度很短.最具代表性的是3种测序技术:①454公司的Roche(454)Genome Sequencer(GS).现在的GS FLX Titanium一次实验(experiment run)能产生一百多万条长度为400 bp的短片段.②Illunima(Solexa)Genome Analyzer(GA).最新的Illumina GAIIx一次实验能产生约2亿条长度为75～100 bp的短片段.③ABI的SOLiD测序平台.目前该技术一次实验能够产生4亿条长度为50 bp的短片段［1］.

在基因组的再测序中，由于已经有了一个可供参考的基因组，需要解决的问题就是把测序得到的短片段和参考基因组进行比较，确定短片段在参考基因组上的位置，从而确定个体基因组的真实序列，这个过程称为短片段的定位过程.短片段的定位过程中一个关键环节是把短片段和参考基因组进行比对.通常进行DNA序列比对使用的是BLAST［2］，SHAHA［3］等算法，但由于高通量测序技术产生的数据量巨大，且片段长度很短，上述算法都无法胜任对测序短片段定位的工作.目前所有的短片段定位算法主要遵循如下2种基本的技术:①基于哈希表的方法.代表方法有MAQ［4］，ZOOM［5］，PASS［6］和SOAP［7］.②基 于Burrows Wheeler Transform(BWT)［8］的方法.代表方法有BOWTIE［9］，BWA［10］和SOAP2［11］.

以上所有的短片段比对算法都存在的问题是一个短片段可能对应参考基因组上许多不同的位置，而算法并没有给出哪个位置可信度最高，从而导致大量短序列产生错误匹配.为解决此问题，本文提出了一种新的……