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

主要研究者：Christina LeslieCo-PI：William斯塔福德Noble合作者：Jason Weston合作者：Andre ElisseeffITR：蛋白质序列比较的机器学习方法：判别式，半监督，可扩展算法研究目标。成对序列比较是生物信息学的“杀手级应用”。在这个任务中，用户用单个序列查询蛋白质数据库，算法返回可能与查询进化相关的序列的排名列表。从共同祖先序列传下来的两个序列-即使它们的序列相似性可能是微妙的-可能具有相似的三维结构，并在细胞中扮演相似的功能角色。 现有的两两序列比对算法主要分为两大类：启发式比对算法（heuristic alignment algorithms），适用于大型数据库，但不能捕捉到蛋白质的细微相似性;和基于蛋白质家族模型的方法，其对于确定序列是否适合特定的家族模型是准确的，但不能评估两个未注释的蛋白质之间的相似性。 流行的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.