文档介绍：东北师范大学硕士学位论文
摘 要
随着高效、自动化的测序技术的出现，生物信息学的中心课题，已经从对基
因的测序，转移至对已测序基因的分析，主要是对基因功能的研究及注释。由于
同源性方法的自身缺陷问题及精度问题，人们开始逐渐重视非同源性方法。非同
源性方法主要是通过序列的属性对归类，进而进行功能预测。系统发育谱法在众
多非同源性方法应用中应用最为广泛。
系统发育谱法于 1999 年由 Pellegrini 提出，随后众多学者从基因参照组选择、
系统发育谱构建、谱相似性分析这三方面对其改进。本文在这些基础之上，先构
建基于权重的系统发育谱，之后交替使用层次聚类法与 K 均值聚类法进行相似
性分析。在谱相似性分析阶段，提出两点改进：一是提出一种新的距离，用于层
次聚类法的聚类阶段。二是从层次聚类法中提取更多信息，为 K 均值聚类法提
供初始信息，更充分的利用层次聚类法的结果，使得 K 均值聚类法的结果更准
确。
目前在聚类算法中，主要应用的是欧式距离。因为我们所处理的样本大都属
于欧式空间，所以采用欧式距离聚类可以得到不错的效果。本文所采用的距离，
是一种非欧空间距离。相比欧式距离，它强化了已知信息对样本距离的影响。它
不仅考虑样本之间的距离，还考量了样本与参照系样本的距离。使用这种新的距
离，可以使我们优先处理与已知参照系相近的样本。
K 均值聚类法的缺陷在于初始条件选取的敏感性：初始聚类数 K 与初始聚类
目标的选取，会对最后的聚类结果产生很大影响。目前对 K 均值算法的改进主
要在初始信息的选取上。前人采用层次聚类与 K 均值聚类结合使用的方法，目
的是利用层次法为 K 均值聚类法提供初始聚类数 K。本文在此基础上，从层次
聚类法的结果中提取更多有用信息，给出 K 均值聚类法的初始聚类目标。
最后，本文用 Escherichia coli K12 基因组作为试验样本，对这些改进进行试
验验证。由试验结果可知，相比与原先的结果，新的算法准确性更高。
关键词：系统发育谱；权重；层次聚类；K 均值聚类；生物学距离；K 均值初始
样本
- I -
东北师范大学硕士学位论文
Abstract
With appearance of the automatic, efficient sequencing technique, the task of
Bioinformatics has transferred to the gene analysis and genome donation. Because of
the shortcomings of the homology method, people pay more and more attention to the
non-homology ways. The classification and function analysis is based on the attribute
of the sequence.
Phylogenetic profiling is a kind of non-homology annotation method using
evolution information. After it was proposed by Pelle