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

发布时间：2018-06-27 16:51

本文选题：结构变异 + 拷贝数变异　；参考：《软件学报》2017年10期

【摘要】：高通量测序技术的发展,极大地推动了基因组结构变异识别的研究.当前,该领域主要使用覆盖度、读分割或片段组装方法来识别变异,但目前的方法识别结果不够准确,敏感度高,对基因组结构变异的信息(如变异序列、变异坐标等)挖掘不充分.插入和删除类型的结构变异统称为indels,在基因组结构变异中最为常见.为此,针对indels的精确识别,提出了基于读分割和动态规划的最优序列匹配算法(optimal split-read matching algorithm,简称OSRM).OSRM算法能将异常读片段以最少的空位打断比对到参考序列上.首先,建立异常读片段与特定参考序列的匹配得分矩阵;然后,建立回溯路径矩阵;最后,用以变异特点设计的得分公式对每条路径进行最优匹配筛选,输出精确识别的indels坐标及序列.实验结果显示,该方法对小中型的indels有很高的识别性能.此外,与读分割法的经典算法Pindel进行了比较,证实OSRM算法在小中型的indels识别方面有更好的效果,可识别更复杂的情况.
[Abstract]:The development of high throughput sequencing technology has greatly promoted the study of the identification of genomic structural variation. At present, the domain mainly uses coverage, read segmentation or fragment assembly methods to identify variations, but the current method is not accurate and sensitive, and the information of genome structure variation, such as mutation sequences, variation coordinates, etc., is excavated. Not enough. The structural variation of insert and delete types is called indels, which is the most common in genomic structural variation. For this purpose, an optimal sequence matching algorithm based on read segmentation and dynamic programming (optimal split-read matching algorithm, simply called OSRM).OSRM algorithm is proposed for the precise identification of indels. First, the matching score matrix of the abnormal read fragment and the specific reference sequence is set up; then, the backtracking path matrix is established; finally, the score formula designed with the characteristic of variation is optimized for each path, and the output is accurately identified with the other indels coordinates and sequences. The experimental results show that this method is used. It has high recognition performance for small and medium indels. In addition, compared with the classical algorithm Pindel of read segmentation method, it is proved that the OSRM algorithm has a better effect on small and medium indels recognition and can identify more complex situations.
【作者单位】：哈尔滨工业大学计算机科学与技术学院;北京建筑大学电气与信息工程学院;
【基金】：国家自然科学基金(61402132,61571163,61532014)~~
【分类号】：Q811.4;TP301.6

【相似文献】