快速准确的获取生物体的遗传信息是生命科学研究的基石,基因组是生物体全部遗传信息的载体。测序技术能够获得基因组的遗传信息,进而较全面的揭示生物体的复杂性和多样性,因而在生命科学研究中具有十分重要的作用。随着科学的进步,下一代测序技术迅速发展并广泛应用,使得生物序列数据的获取效率和费用成本的快速下降都达到了前所未有的程度,这些对基因组的深度测序和重测序研究产生了极大的推动作用。序列数据生产速度越来越快,由此产生了数量巨大的生物序列数据,而如何高效准确的对大数据量的生物序列数据进行分析和比较,成为了生物信息学领域的新挑战。近几年来计算机运算性能的增长趋于缓慢,为应对大数据时代的需求出现了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识别和分析的研究工作。