基于读分割最优匹配的indels识别算法

来源：软件学报杂志2017年第10期北京时间：

作者：王春宇,潘俊,郭茂祖,刘晓燕,刘扬,刘国军

单位：王春宇，哈尔滨工业大学 计算机科学与技术学院, 黑龙江 哈尔滨 15000111,潘俊，哈尔滨工业大学 计算机科学与技术学院, 黑龙江 哈尔滨 15000102,郭茂祖，北京建筑大学 电气与信息工程学院, 北京 10004403,刘晓燕，哈尔滨工业大学 计算机科学与技术学院, 黑龙江 哈尔滨 15000104,刘扬，哈尔滨工业大学 计算机科学与技术学院, 黑龙江 哈尔滨 15000105,刘国军，哈尔滨工业大学 计算机科学与技术学院, 黑龙江 哈尔滨 15000106

摘要：高通量测序技术的发展，极大地推动了基因组结构变异识别的研究.当前，该领域主要使用覆盖度、读分割或片段组装方法来识别变异，但目前的方法识别结果不够准确，敏感度高，对基因组结构变异的信息（如变异序列、变异坐标等）挖掘不充分.插入和删除类型的结构变异统称为indels，在基因组结构变异中最为常见.为此，针对indels的精确识别，提出了基于读分割和动态规划的最优序列匹配算法（optimal split-read matching algorithm，简称OSRM）.OSRM算法能将异常读片段以最少的空位打断比对到参考序列上.首先，建立异常读片段与特定参考序列的匹配得分矩阵；然后，建立回溯路径矩阵；最后，用以变异特点设计的得分公式对每条路径进行最优匹配筛选，输出精确识别的indels坐标及序列.实验结果显示，该方法对小中型的indels有很高的识别性能.此外，与读分割法的经典算法Pindel进行了比较，证实OSRM算法在小中型的indels识别方面有更好的效果，可识别更复杂的情况.

关键词：结构变异;拷贝数变异;动态规划;读分割;精确识别

基金资助：国家自然科学基金（61402132，61571163，61532014）