DNA片段拼接中重复序列算法研究.pdfVIP

计算机科学2006Voi. 33N. 7 DNA 片段拼接中重复序列算法研究＊） 王 磊 张祖平 陈建二 （中南大学信息科学与工程学院 长沙4 10083 ） 摘 要 本文主要研究DNA 片断拼接中重复序列信息识别算法。包含大量重复信息的DNA 序列，其重构是大规模 DNA 片段拼接所面临的实际困难之一。针对目前大多数拼接算法对于重复段的处理采用效率较低的反复迭代算法 的特点，提出了基于k-mer 子串的重复段分析方法，充分考虑了拼接中可能的分割点，设计与分析了识别重复序列并 提高序列一致性的高效算法。 关键词 生物信息学，片段拼接，重复片断，k-mer 子串 Algorithms of Repeats in DNA Fragment Assembly WANG Lei ZHANG Zu-Ping CHEN Jian-Er （Schooi of Information Science Engineering ，Centrai South University ，Changsha 4 10083 ） Abstract The paper mainiy studies repeats anaiysis in DNA fragment assembiy. One of the practicai difficuities that remain in iarge-scaie DNA fragment assembiy is the correct reconstruction of DNA seguences that contain repeats. Aiming at the char- acteristic of iterativeiy deaiing with repeats by most fragment assembiers which are very inefficient，the paper not oniy proposes a generai method of kmer-based repeat anaiysis that fuiiy considers aii possibie break points in the assembiy ，but aiso designs and anaiyses high-performance aigorithms to move repeats as weii as improve overaii consistency. Keywords Bioinformatics ，Fragment assembiy ，Repeat ，k-mer substring mer 子串快速确定重复序列的位置。这种方法适用于任何遵 ! 引言 循如下几个步骤的序列拼接方法的预处理中： 比较片断集 ! 为了适应复杂生物（例如人等）大规模、长片断的DNA 合中的所有片断，获得可能存在的重叠部分（Overiap ）； 建 序列测定的需要，当前世界范围内的主要测序中心以及重要 立所有片断间的相互组合关系（Layout ），以片断为顶点，重叠 的测序工程都普遍采用了鸟枪（Shotgun ）测