针对短测序片段的基因序列拼接算法  

Algorithm of genomic sequence assembly based on short reads

作　　者：郭佳[1] 杨云麟[1] 

机构地区：[1]四川大学计算机学院,四川成都610065

出　　处：《计算机工程与设计》2012年第5期1832-1836,共5页Computer Engineering and Design

基　　金：国家自然科学基金项目(60903318;60832011);国家自然科学基金重点项目(60736046);国家973重点基础研究发展计划基金项目(2009CB320803)

摘　　要：为了获得高效的拼接结果,针对新测序技术产生的较短测序片段,提出了通过对测序片段编码,将其映射到能够快速查找的自定义表中,结合高效位并行字符串模糊匹配算法———BPM,从自定义表中寻找较长连通路径的方法,实现了对短测序片段的快速拼接。实验结果表明,该算法针对500M的高质量源数据,在耗时136s的情况下,准确度可达79%,覆盖度可达82%;针对错误率为0.1%的500M源数据,在耗时150s的情况下,准确度可达72%,覆盖度可达73%。在短时间内较好的完成了拼接任务。The sequences（also called read） generated by new technologies are very short.For these short reads,in order to get the high effective sequencing results,after be encoded,they are mapped into a customized table,then an effective bit parallel fuzzy string match algorithm is employed,that is,BPM.Finally a long connected path in the customized table is found to achieve the rapid genomic sequence assembly.The experimental results show that,under the condition of running the algorithm on the 500M high quality source data,the time consumes 136s,the accuracy rate achieves 79%,and the coverage rate achieves 82%.For 500M source data contains 0.1% error rate,the time consumes 150s,the accuracy rate achieves 72%,and the coverage rate achieves 73%.The task is well done in a short time.

关 键 词：短测序片段 快速查找表 四进制整数 BPM(位并行匹配算法) 连通路径 

分 类 号：TP274[自动化与计算机技术—检测技术与自动化装置]