生物信息学是一个新兴的跨学科研究领域,通过采用计算方法来解决分子生物学问题,最终目的是能够发现隐藏于海量生物数据中的生物模式和信息,并应用这些信息来提高对一些重要的生物运行机制的理解。生物序列分析则是生物信息学领域重要的基础性研究工作。近年来,随着生物学实验数据的爆炸式增长,机器学习方法在生物序列分析和重要信息的提取中发挥着越来越重要的作用。机器学习通过建立适当的统计模型,可以捕捉隐藏于大量实验数据中的复杂模式并基于它们做出决策。因此,机器学习方法特别适用于类似生物信息学的拥有大量数据但相应理论很不完善的领域。本文围绕机器学习方法在生物序列分析中的应用展开研究,主要做了以下工作：1、求解多序列的最优比对是一个NP问题,目前已有大量的方法和程序被开发出来用于蛋白质多序列比对。但是,这些方法大多数都是使用优化得分函数的方法获得最佳或接近最佳的比对,因此只能产生一个单一的比对结果。最近的研究工作发现,通过最优化得分函数的方法取得的最佳序列比对结果,往往并不是最具有生物学意义的比对。因此,本文提出一种基于集成学习的多蛋白质序列比对方法,将隐马尔可夫模型作为集成学习中的基分类器,在对训练集中的序列进行排序后依次与隐马尔可夫模型进行比对,根据比对结果优化模型参数,最后生成一组分数较高的比对结果。在构建集成学习系统时,提出并证明了一种双序列比对方法,可以精确计算出两个给定蛋白质序列的具有领先分数的若干个比对结果,其计算的时间复杂度为二次函数。此外,针对蛋白质二级结构信息对序列比对结果的影响,在之前模型的基础上进行改进,通过一个匹配矩阵实现蛋白质二级结构的匹配分数计算,并初步分析和探讨了引入二级结构信息对不同测试组的比对精度影响。2、针对目前基于共变模型的非编码RNA序列搜索软件计算效率低的缺点,对传统共变模型进行了改进。首先,对非编码RNA家族的成员序列与该家族的共变模型比对的结果进行了分析,结果表明在共变模型的任何状态,最优比对的子序列长度大多与一致结构的长度相差不多。据此,将RNA家族的二级结构分成若干个基本的结构单元,其中每一个结构单元代表二级结构中的一个茎或环,并为每个结构单元增加了长度限制。设计了一种结构单元的长度限制计算方法,在计算出上、下限的同时,给出相应的置信度。并根据各个结构单元的长度分布对家族中的序列在进化过程中出现插入和删除的次数进行了限定,从而显著降低了序列结构比对的计算时间。3、转录因子结合位点在基因调控中起着非常重要的作用,准确预测它们在启动子区域的位置可以有助于理解特定基因的表达水平的调节。针对转录因子结合位点的识别,已经开发出了很多的计算方法和工具,但其预测的准确度并不理想。本文提出了一种基于图论的转录因子结合位点的预测方法。通过一个无向有权图来模拟同源基因的启动子区域内的所有子序列和它们之间的关系,从而把问题转化为图的最优化问题。同时,为了提高寻找问题的最佳解决方案的速度,提出了一种预处理技术,可以显著降低图的大小。最后,设计了一种枚举算法搜索图模型中的最大边权团,最大边权团对应的子序列即为预测的转录因子结合位点。4、传统的聚类方法在用于DNA微阵列数据分析时,多数只能生成一种聚类结果,无法识别出与多组不同的基因表达模式相类似的基因。针对该问题,提出一种基于图形模型和图割算法的DNA微阵列数据聚类方法,将样本空间的整个数据集表示为一个有权图,然后迭代地求解图的最小割权值和第二小割权值,根据图割,将图分割为子图。此外,在数学上证明了图的第二最小割可以在多项式时间内算出。对高连通图的定义进行引申后,用于无向有权图中,并将高连通图的判据作为图分割的终止判据。