ITR: Machine learning approaches to protein sequence comparison: discriminative, semi-supervised, scalable algorithms

合作者：Jason Weston合作者：Andre ElisseeffITR：蛋白质序列比较的机器学习方法：区分、半监督、可扩展算法研究目标。两两序列比对是生物信息学的“杀手级应用”。在这项任务中，用户用单个序列查询蛋白质数据库，算法返回可能与查询在进化上相关的序列的排序列表。从一个共同的祖先序列衍生出来的两个序列--尽管它们的序列相似性可能很微妙--可能具有相似的三维结构，并在细胞中扮演类似的功能角色。因此，识别细微的序列相似性对于推断蛋白质的进化、功能和结构是有用的。几乎所有现有的成对序列比对算法都可以分为两类：启发式比对算法和基于蛋白质家族模型的方法，启发式比对算法可扩展到大型数据库，但可能无法捕获细微的蛋白质相似性；基于蛋白质家族模型的方法可以准确地确定一个序列是否符合特定的家族模型，但不能评估两个未注释的蛋白质之间的相似性。流行的PSI-BLAST算法是这两种方法的混合：它试图动态地从单个查询序列迭代构建模型，然后在数据库中搜索符合该模型的序列。虽然PSI-BLAST是一种有效的方法，但它并不是检测更多远程蛋白质关系的最准确的方法。我们在这个建议中追求的方法是全新的：我们使用机器学习算法对来自整个蛋白质空间的样本进行离线训练，包括那些带有家族注释和未注释的序列，以便在运行时，我们训练的模型可以准确地预测哪些数据库序列与查询相关。换句话说，我们希望将学习引入到一般的序列比较问题中，而不是求助于更有限的基于家庭的模型方法。这项研究的一个主要目标是开发利用问题的附加或隐藏结构的算法。为此，我们试验了一些学习算法，包括约束聚类、邻域平均、使用分层标签和分类器集成、降维技术(如非负矩阵分解)和基于核的半监督方法。除了算法开发，我们计划开发一个软件实现和网络界面，使我们的技术可用于生物界。在整个研究过程中，我们将强调可扩展的技术。我们希望实际预测时间很快，这样用户就可以输入新的查询序列，并通过Web界面从数据库中实时检索相关序列的排序列表。因此，我们专注于两个功能：离线训练，它允许我们在训练过程中利用更昂贵的计算，以便快速预测；使用快速字符串核，这是我们在蛋白质分类方面的一种技术，将使运行时速度加快。更广泛的影响。成对序列比较是生物信息学和基因组学中的一个中心问题，我们通过最先进的机器学习技术提高蛋白质序列比较的性能和可扩展性的技术将广泛应用于生物学家和生物信息学家。作为我们提案的一部分，我们将生产的软件实施和网络界面将使我们的技术可供生物界使用。我们研究的所有规格、数据集和结果都将通过我们的网站公开提供。所有新的算法也将在出版物中描述，以便分发给机器学习社区。最后，我们注意到，我们的序列比较问题的学习挑战--例如，在具有大量未标记数据而只有少量已标记数据的环境中学习--发生在机器学习的许多其他应用领域，如文本分类和信息检索。因此，我们的研究将在许多应用学习和数据驱动领域产生影响。

PI: Christina LeslieCo-PI: William Stafford NobleCollaborator: Jason WestonCollaborator: Andre ElisseeffITR: Machine learning approaches to protein sequence comparison: discriminative, semi-supervised, scalable algorithmsResearch Goals. Pairwise sequence comparison is the ``killer app'' of bioinformatics. In this task, the user queries a protein database with a single sequence, and the algorithm returns a ranked list of sequences thatare likely to be evolutionarily related to the query. Two sequences that are descended from a common ancestral sequence - even though their sequence similarity may be subtle -- are likely to have similar three-dimensional structures and fill similar functional roles in the cell. Hence, recognizing subtle sequence similarities is useful for inferring protein evolution, function and structure.Almost all existing algorithms for pairwise sequence comparison fall into one of two categories: heuristic alignment algorithms that are scalable to large databases but can fail to capture subtle protein similarities; and approaches based on protein family models, which are accurate for determining whether a sequence fits a particular family model but cannot evaluate similarity between two unannotated proteins. The popular PSI-BLAST algorithm is a hybrid of the two approaches: it tries to iteratively build a model from a single query sequence on the fly and then searches the database for sequences that fit the model. While efficient, PSI-BLAST is known not to be the most accurate method for detecting more remote protein relationships.The approach that we pursue in this proposal is fundamentally new: we use machine learning algorithms to train offline on examples from the full space of proteins, both those with family annotations and unannotated sequences, so that at run-time, our trained model can accurately predict which database sequences are related to the query. In other words, we want to introduce learning into the general sequence comparison problem, without resorting to a more limited family-based model approach. One primary goal of this research is the development of algorithms that exploit the additional or hidden structure of the problem. To this end, we experiment with a number of learning algorithms, including constrained clustering, neighborhood averaging, use of hierarchical labels and ensembles of classifiers, techniques for dimensionality reduction like non-negative matrix factorization, and kernel-based semi-supervised approaches.In addition to algorithm development, we plan to produce a software implementation and web interface that will make our techniques available to the biological community. Throughout our research, we will emphasize techniques that are scalable. We want the actual prediction time to be fast, so that a user can enter a newquery sequence and retrieve a ranked list of related sequences from the database in real time via a web interface. Thus we focus on two features: training offline, which allows us to take advantage of more expensive computation in the training process so that the predictions can be fast; and use of fast string kernels, a technique from our work on protein classification that will enable run-time speed-up. Broader Impacts. Pairwise sequence comparison is a central problem in bioinformatics and genomics, and our techniques for improving performance and scalability of protein sequence comparison through state-of-the-art machine learning techniques will be broadly useful to biologists and bioinformaticians. The software implementation and web interface that we will produce as part of our proposal will make our techniques available to the biological community. All specifications, datasets, and results from our research will be made publicly available via our web site. All new algorithms will also be described in publications for dissemination to the machine learning community. Finally, we note that the learning challenges of our sequence comparison problem -- for example, learning in a setting with a large amount of unlabelled data and only a small amount of labelled data -- occur in many other applied areas of machine learning, such as text classification and information retrieval. Thus our research will have impact in many applied learning and data-driven fields.