基于变长子串的DNA重复序列预归并屏蔽方法

2012-09-08杨进才

武汉理工大学学报(信息与管理工程版) 2012年1期

关键词：方法

蔡葵，杨进才

(1.武汉理工大学华夏学院，湖北武汉 430223;2.华中师范大学计算机科学系，湖北武汉 430079)

针对 DNA 序列拼接，REPS［1］方法通过度量定长子串来确定重复序列。文献［2-3］以此为基础，提出了各自的定长为k的重复序列识别屏蔽方法。文献［4］进一步提出了预归并的思想，但仍然局限于定长子串识别方法，对偏长的DNA重复序列处理能力不强，识别不够精确。

笔者在PreMerged方法的基础上，引入HUANG［5］等提出的 Superword array 概念，继续预归并思想，提出了利用变长子串来识别且屏蔽重复序列的VPreM方法。模拟实验证明，较之Pre-Merged方法，VPreM方法识别重复序列的精确度更高，并且可以更大规模地缩减shotgun集合规模。

1 基于变长子串的预归并算法

1.1 基本思想

将shotgun集合中所有fragments片段末尾加上字符#，并串连成一大字符串F，为F中每个字符按顺序编号。由字符集{A，G，C，T}上w个字符组成的字符串，就是一个长为w的word，长为w的word一共有4w个。将这4w个word按字母顺序编号，形成一个word字查找表。表1为w值为2的word字查找表。

表1 w为2的word字查找表

大字符串 F上以p位置起始，长为 w的word，其在查找表中的编号Nu，就是p位置的编码，记为Code(p)=Nu。若word中含#，则编号统一设为Nu=-1。图1为一个大字符串F编码示意图。

通过编码可以找出任意两个fragments之间，连续h个长为w的word组成的重复部分repeats。假设shotgun集合中fragments总数目为n，可以推导出h及w的取值满足h×w≥log4n。确定h和w的值之后，就可以为大字符串F编码。然后根据不同fragments之间编码的连续相同性(变长子串)，来进行重复序列识别及预归并屏蔽工作。