【作者】 王春宇；

【导师】 郭茂祖；

【作者基本信息】 哈尔滨工业大学 ， 计算机科学与技术， 2015， 博士

【摘要】 快速准确的获取生物体的遗传信息是生命科学研究的基石,基因组是生物体全部遗传信息的载体。测序技术能够获得基因组的遗传信息,进而较全面的揭示生物体的复杂性和多样性,因而在生命科学研究中具有十分重要的作用。随着科学的进步,下一代测序技术迅速发展并广泛应用,使得生物序列数据的获取效率和费用成本的快速下降都达到了前所未有的程度,这些对基因组的深度测序和重测序研究产生了极大的推动作用。序列数据生产速度越来越快,由此产生了数量巨大的生物序列数据,而如何高效准确的对大数据量的生物序列数据进行分析和比较,成为了生物信息学领域的新挑战。近几年来计算机运算性能的增长趋于缓慢,为应对大数据时代的需求出现了Map Reduce、Spark等云计算技术,但目前生物信息领域的各种工具和方法还未能充分利用这些新技术。因此,本文以序列分析为基础,利用Map Reduce技术结合序列比对、串和图等算法,深入研究了高通量序列拼接与分子标记识别两方面的几个问题,主要内容如下。(1)提出了基于Map Reduce的高通量序列数据的聚类分析算法。生物序列聚类可以为下游序列分析工作提供基础,高通量测序也为序列聚类提出了新内容和新挑战。针对这一问题,本文提出了基于两种相似度的结合Map Reduce技术的贪心聚类方法。首先,从相似序列会共享一定数量k-mer这一事实出发,本文提出了基于窗口内非交叠共享k-mer计数的相似度计算方法,可以过滤掉不相关序列间的比对计算,从而大幅度提高比对效率;然后,对于相似序列的精确比对,本文提出了基于共享k-mer扩展块的块比对相似度计算方法。利用本文方法可对大规模序列数据如EST、高通量测序读片段等进行聚类分析。(2)提出了基于序列聚类和Seeds Graph的高通量测序片段拼接算法。全基因组高通量测序数据的拼接,主要困难在于高通量序列数据读长短、数量大和错误率高。本文针对这三方面的困难提出了基于Map Reduce和序列聚类的全基因组de novo拼接方法Seeds Graph。该方法利用云计算平台解决数据量大的问题,用序列聚类将短片段以簇表示,并定义可容错的seed结构来纠正测序错误。然后利用seed为顶点建立的SeedsGraph图来指导测序片段的拼接过程。最后,本文采用路径相容分析技术和双端读片段信息方式解决重复序列导致的复杂路径问题。实验表明Seeds Graph有良好的可扩展性,可处理较大规模基因组的拼接问题。(3)提出了多供体高通量测序数据的基因组结构变异分子标记识别算法。目前对生物个体重测序的研究普遍存在测序对象数量较多而测序深度不够的现象。在这种测序个体较多但深度都不大的数据中进行全基因组结构变异识别,往往因为深度不够而不能获得准确的结果。本文针对这一问题,提出了基于多供体高通量重测序数据的全基因组结构变异识别方法。该方法利用Map Reduce技术解决数据量巨大的问题,结合双端读片段和读片段分隔方法进行结构变异事件的识别;利用改进的仿射空位罚分的半全局序列比对算法,预测结构变异精确的断点位置。(4)综合本文在序列分析的算法成果,设计并实现了基于同源搜索和集成分类的mi RNA分子标记识别方法。该方法利用已知mi RNA为参考,对EST或高通量测序数据进行同源搜索,使用RNAfold软件分析发夹环结构,获得粗略的mi RNA前体候选集。为了解决该候选集中假阳性率过高的不平衡分类问题,本文提出了基于投票机制的集成学习分类方法。利用已知mi RNA作为正例和适当选择的反例以不平衡数据分类问题的策略训练多种分类器,再集成为一个单独的分类器,并对候选集进行分类。利用该方法可得到输入数据集中高可信度的miRNA候选,可以用于指导下游mi RNA识别和分析的研究工作。更多还原

【Abstract】 In the research of life science, it is a great significance that rapid and accurate acquiring organism genetic information, which is entirely stored in organism genome. Sequencing technology successfully decipher complicated and multifarious genome comprehensive information among organisms, and advanced the field of researchers’ vision. Recent scientific discoveries that resulted from the application of nextgeneration sequencing(NGS) technologies highlight the striking impact of these fast inexpensive massively parallel platforms on genetics. A new challenge of plenty of data comes into bioinformatics, and an urge demanding for efficient algorithms in massive data analysis. Genome has been sequenced increasingly faster and relevant data has been accumulated strikingly bigger. On the contrary is the performance enhancement of computer tends to slow down in recent years, and then new cloud computing technologies like MapReduce or Spark emerges for present big data processing. However, these new technologies have not a sufficient employment in bioinformatics research. Therefore, with the assistance of basic sequence comparison techniques, strings and graphs algorithms, and Map Reduce technology, we make an intensive study of several critical issues in NGS sequences assembly and molecular biomarker detection. The main contributions of this dissertation are as followings.(1) A clustering method is proposed for NGS data based on Map Reduce.Biological sequence clustering is a classical research topic in bioinformatics for the assistance of downstream analysis. We propose a new greedy clustering method based on Map Reduce with two new sequence similarity measurement. Based on the fact that two similar sequences should share a certain number of k-mers, we present an approximate sequence similarity algorithm by the counting of sharing k-mers which purge unnecessary computation between unrelated sequences. For similar sequences, we present an accurate sequence similarity algorithm by blocks alignment extended from sharing k-mers which further optimized either. With our method, large scale sequences like ESTs or NGS reads can be clustered efficiently.(2) A de novo NGS whole genome assembly method, Seeds Graph, is proposed based on sequences clustering and Map Reduce.De novo whole genome assembly in NGS data hindered by large number of reads, short length and higher base-call error rate. Seeds Graph is scalable for large number of sequences by Map Reduce. We define a seed structure for the representation of sequences clusters, and build graph, Seeds Graph, with seeds as vertices. It use a serious of seeds denoting consensus for reads to avoid short length. Because seed has approximate string match design, It can resolve high error rate in a certain degree. With the help of compatible path analysis, Seeds Graph can handle complex paths in the graph.(3) A genome structural variation biomarker detection method, md SV, is proposed for multiple donors NGS data.For a quick view of relations between phenotype and genotype in organisms, a prevalence strategy is to sequence more individuals with relative less coverage instead of a single deep one. Whole genome structural variation detection results badly in these data. Therefore we proposed a detection method supporting multiple donors NGS data, called md SV, which utilize paired-end and split-read techniques and multiple dataset to detect more structural variations. And with a modified alignment algorithm, mdSV can predict precise breakpoint positions of structural variations.(4) With the integration of sequence comparison algorithms in this work, we design and implement a software for mi RNA biomarker detection from ESTs or NGS data based homologous search and ensemble learning method.In this tool, we search homologous sequences in ESTs or NGS data by references of known mi RNA prematures, and then analysis hairpin structure by RNAfold, then get a rough candidate set of mi RNA precursors. This set is a typical imbalance classification problem because of high false positive rate. We propose an ensemble classifier with voting policy for the classification in this set. We choose known mi RNA precursors as positive samples and deliberately selected negative samples to train multiple single classifiers in a way of imbalance data, and then ensemble them to a single classifier. A high confidence mi RNA precursors set can be predicted from our software, and could be used for downstream of mi RNA analysis and detection research.更多还原