生物序列数据分析是生物信息学的核心任务,是了解生物大分子结构和功能、生物进化历程中联系和差异的主要途径。由于测序技术迅猛发展,产生了大量的核苷酸等生物序列数据,同时随着千人基因组和地球生物基因组计划的开展,越来越需要提升序列分析算法的处理能力。生物序列分析中多序列比对（Multiple Sequences Alignment,MSA）是其中重要的研究问题,其分析结果可为后续的序列保守区域和功能模体的识别和量化、估计序列之间的进化差异、祖先序列的分析提供更多的生物信息。对于大规模核苷酸序列,已有的基于动态规划方法的MSA算法计算复杂度高,基于划分的MSA算法限于短种子划分存在位置过多和不准确问题。因此,本文以面向核苷酸序列的多序列比对为研究背景,先对于同源序列集,提出了基于长种子的多序列比对基础算法,以及改进和优化了基础算法中索引关键技术;然后对于非同源序列集,提出了一种高效的多序列分组算法,使得多序列比对基础算法可应用于更一般序列集。论文主要工作及创新如下:1.基于长种子划分的多序列比对方法多序列比对需同时对多条序列进行处理,其计算复杂性随序列条数和序列长度的增大而增加。因此,大多数经典的MSA算法难以处理大规模的多序列数据集,尤其是长序列情形。最近的一些高效多序列比对算法采用了分治策略,将序列集合进行垂直划分或水平划分,其中垂直划分更能有效地解决长序列带来的复杂性问题。在基于垂直划分的多序列比对方法中,选择用于序列划分的公共子串（种子）是其中的关键技术,它直接影响序列比对的准确性和时间成本。因此,本文提出一种新的基于长种子而选择较优划分链的算法,以提高垂直划分的多序列比对方法性能。该方法采用FM-index索引技术快速找到序列上长公共种子,再采用复杂性低于动态规划的启发式方法从侯选锚点中找出一个较优的划分链,这样将原序列集按划分种子链垂直划分为若干组的短序列集,然后完成各组短序列的比对后再拼接为完整的比对计算。计算实验结果表明,在处理长的病毒和细菌基因组和人类线粒体基因组时,我们提出的算法FMAlign性能好于MAFFT、HAlign和FAME等现有的基线MSA算法。2.多序列长公共种子提取方法长公共种子出现的位置少,且更可能是实际的匹配,因此长公共种子提取对于多序列比对方法是至关重要的。目前,长公共种子的提取都采用朴素算法,即先采用FM-index或者Hash索引技术提取固定长度的短公共种子再进行拼接,这些算法成本较高。为此,本文提出了一种新的多序列长公共种子提取算法,利用字典序排序的多条后缀共前缀的性质高效提取长公共种子。该算法基于基础数据后缀数组（Suffix Array,SA）、BWT（Burrows-WheelerTransform）和最长公共前缀数组（Longest Common Prefix,LCP）,进行修改和优化而得到的。提出的算法根据SA数组和LCP数组快速确定多序列的某个公共串,通过BWT值计算该公共串是否能继续增长,以便找到更长的公共串（长公共种子）。为减少索引内存,进一步设计了 LCP采样方法。计算实验结果表明,在多序列集上,提出的方法bvMEM具有较好的性能,计算速度至少是已有工具的2倍。设计的索引应用到FMAlign多序列比对算法上,时间性能得到明显提升。3.基于公共种子度量的多序列分组方法对于来非同源序列,不仅比对时间较长,而且未必能得到生物学上可信的比对,因此需要对序列集进行同源分组,然后再进行各组序列的多序列比对。现有多序列分组包括指定参考序列（Reference-based）和未指定参考序列（Reference-free）两类,前者采用朴素的序列比对算法可以完成分组;后者使用贪心策略选择每个组的中心序列,然后通过序列比对进行分组,因而中心序列选择好坏直接影响分组结果。为此,本文提出了一个新的序列分组算法,不再依赖于选择的中心序列,而是采用DBSCAN算法将紧密关联的序列分为一组。该方法依据定长公共种子数量计算序列相似度,对前面长公共种子提取算法bvMEM进行修改,使之能够快速计数多个序列之间的公共种子数量。计算实验结果表明,在测序序列集上和基因组序列集上,提出的算法分组准确率高于现有的经典算法cd-hit和vserach,计算时间明显好于这些算法。