ABI Innovation: New methods for multiple sequence alignment with improved accuracy and scalability

多序列比对(MSA)是生物信息学中最基本的步骤之一，它将一组分子序列(即DNA、RNA或氨基酸序列)排列在基质中以识别相应的位置。MSA计算是许多生物分析的基本第一步。由于其广泛的适用性和重要性，许多MSA方法已经被开发出来并在今天被广泛使用。不幸的是，许多现实世界的生物数据集都具有一些特征(例如，大尺寸和零碎的序列)，这使得精确的MSA计算变得非常困难。由于估计不佳的比对会导致下游生物分析中的错误，因此需要新的MSA技术来在困难的数据集上产生准确的比对。该项目将极大地提高MSA方法的精度，并可以分析国家不同生物项目中正在组装的大型异质序列数据集。该项目还向女子学院和少数族裔服务机构以及暑期软件学校提供了大量的外联部分，以培训生物学家使用该项目软件。多重序列比对(MSA)和系统发育估计是两个非常基本的生物信息学问题，它们位于机器学习、统计估计和进化与结构生物学的交叉点上。MSA在构建进化树，了解蛋白质的功能和结构，检测蛋白质之间的相互作用，甚至基因组组装方面具有特别重要的作用。大规模的MSA和系统发育估计还需要高性能的计算和并行算法，以便提供足够的可扩展性。该团队将开发新的机器学习技术，以极大地改进MSA方法，从而也改善系统发育估计，因为它依赖于准确的多序列比对。该项目的核心是算法开发，利用各种机器学习技术(包括隐马尔可夫模型)、统计估计方法(特别是贝叶斯MCMC和最大似然法)和新的算法策略，所有这些都侧重于提高可伸缩性和准确性。有关该项目的更多信息，请访问：http://tandy.cs.illinois.edu/MSAproject.html

Multiple sequence alignment (MSA) is one of the most basic bioinformatics steps, in which a set of molecular sequences (i.e., DNA, RNA, or amino acid sequences) are arranged inside a matrix to identify corresponding positions. MSA calculation is a fundamental first step in many biological analyses. Because of its broad applicability and importance, many MSA methods have been developed and are in wide use today. Unfortunately, many real world biological datasets have features (large size and fragmentary sequences, for example) that make accurate MSA calculation very difficult. Because poorly estimated alignments result in errors in downstream biological analyses, new MSA techniques are needed that can produce accurate alignments on difficult datasets. This project will develop MSA methods with greatly improved accuracy, and that can analyze the large and heterogeneous sequence datasets being assembled in different biology projects nationally. The project also has a substantial outreach component to women's colleges and minority serving institutions, and summer software schools to train biologists in the use of the project software.Multiple sequence alignment (MSA) and phylogeny estimation are two very basic bioinformatics problems, which sit at the intersection of machine learning, statistical estimation, and evolutionary and structural biology. MSA has particular importance in constructing evolutionary trees, understanding the function and structure of proteins, detecting interactions between proteins, and even genome assembly. Large-scale MSA and phylogeny estimation also require high performance computing and parallel algorithms, in order to provide adequate scalability. The team will develop new machine learning techniques to greatly improve MSA methods, and hence also phylogeny estimation, since it depends on accurate multiple sequence alignments. The core of this project is algorithm development, utilizing a variety of machine learning techniques (including Hidden Markov Models), statistical estimation methods (especially Bayesian MCMC and maximum likelihood), and novel algorithmic strategies, all focused on improving scalability and accuracy. More information about the project can be found at: http://tandy.cs.illinois.edu/MSAproject.html