随着生物信息技术的不断发展,其数据量增长惊人,特别是随着二代测序技术的成熟,DNA与RNA序列的数据量呈爆炸式喷发,因此对生物大数据的分析和研究也变得更加迫切。序列的比对算法是生物信息研究中最基础的操作,对生物研究的其他各方面的工作提供重要支持。由于传统序列比对算法一般时间和空间复杂度较高,因此降低序列比对算法的复杂性和(或)提高精确度,是相当重要的。本文针对这些问题,通过对序列比对和序列聚类等问题进行了探讨,提出了两种新的算法,这些新算法在降低时间复杂性和提高精确度方面,都做出了贡献。概况而言,主要完成了以下两点工作:1.针对现有序列比对算法存在的时间复杂度高的问题,提出了一种新的基于权重的算法(weight-based Kendall algorithm,WK2)。首先,用后缀树提取序列的特征;其次,应用本文定义的基于权重的Kendall相关系数来计算序列的相似度。规避了传统算法使用动态程序对序列进行比对,从而减小时间复杂度。实验表明WK2算法执行时间复杂度为O(nlogn),n为数据集合大小,相比业界现存O(n2)复杂度的算法是较大的提高。该算法对不同结构的数据集,在时间和空间复杂度上都有良好的实验结果,验证了该算法的有效性。2.针对现存算法时间效率不高、准确率较低、聚类结果的生物意义不够明显的问题,提出了基于信息熵的局部敏感哈希聚类算法。使用p稳定分布的局部敏感哈希方法来降低查找相似序列的时间复杂度;利用位置信息熵作为哈希函数的特征向量来提高准确率;在评估聚类结果时使用编辑距离作为度量指标以增强生物学上的可解释性。该方法使用基于位置信息的标准熵作为局部敏感哈希函数的特征向量对生物序列进行聚类,其实验结果表明算法执行时间和数据集合大小成线性相关,对不同量级的数据集都有良好的实验结果,并且在模拟数据和真实数据的实验结果均验证了该算法的有效性。序列比对是生物信息学研究的基础,该研究通过对生物序列比对问题和生物序列聚类算法的改进,能够提供新的方法来降低对生物序列的前期筛查和从大量数据中快速找到感兴趣的序列。除了生物学中的DNA序列,RNA序列,蛋白质序列等,该研究中提出的方法还有可能被应用于其他有序列特性的数据中,比如网络流数据。在当前的大数据环境下,这些方法有着其潜在的应用前景。