Department of Computer Science, University of Texas-Pan American, Edinburg, TX 78539, USA.
BMC Bioinformatics. 2010 Jan 18;11 Suppl 1(Suppl 1):S34. doi: 10.1186/1471-2105-11-S1-S34.
Proteins show a great variety of 3D conformations, which can be used to infer their evolutionary relationship and to classify them into more general groups; therefore protein structure alignment algorithms are very helpful for protein biologists. However, an accurate alignment algorithm itself may be insufficient for effective discovering of structural relationships among tens of thousands of proteins. Due to the exponentially increasing amount of protein structural data, a fast and accurate structure alignment tool is necessary to access protein classification and protein similarity search; however, the complexity of current alignment algorithms are usually too high to make a fully alignment-based classification and search practical.
We have developed an efficient protein pairwise alignment algorithm and applied it to our protein search tool, which aligns a query protein structure in the pairwise manner with all protein structures in the Protein Data Bank (PDB) to output similar protein structures. The algorithm can align hundreds of pairs of protein structures in one second. Given a protein structure, the tool efficiently discovers similar structures from tens of thousands of structures stored in the PDB always in 2 minutes in a single machine and 20 seconds in our cluster of 6 machines. The algorithm has been fully implemented and is accessible online at our webserver, which is supported by a cluster of computers.
Our algorithm can work out hundreds of pairs of protein alignments in one second. Therefore, it is very suitable for protein search. Our experimental results show that it is more accurate than other well known protein search systems in finding proteins which are structurally similar at SCOP family and superfamily levels, and its speed is also competitive with those systems. In terms of the pairwise alignment performance, it is as good as some well known alignment algorithms.
蛋白质具有多种 3D 构象，可以用于推断它们的进化关系，并将它们分类为更一般的组别；因此，蛋白质结构比对算法对蛋白质生物学家非常有帮助。然而，一个准确的比对算法本身可能不足以有效地发现数以万计的蛋白质之间的结构关系。由于蛋白质结构数据的数量呈指数级增长，因此需要一个快速而准确的结构比对工具来访问蛋白质分类和蛋白质相似性搜索；然而，当前比对算法的复杂性通常过高，无法实现完全基于比对的分类和搜索。
我们开发了一种高效的蛋白质两两比对算法，并将其应用于我们的蛋白质搜索工具中，该工具以两两的方式将查询蛋白质结构与蛋白质数据库（PDB）中的所有蛋白质结构进行比对，以输出相似的蛋白质结构。该算法可以在一秒钟内比对数百对蛋白质结构。给定一个蛋白质结构，该工具可以在一台机器上 2 分钟内，在我们的 6 台机器集群中 20 秒内，从 PDB 中存储的数万结构中高效地发现相似结构。该算法已完全实现，并可在我们的计算机集群支持的在线网络服务器上使用。
我们的算法可以在一秒钟内处理数百对蛋白质的比对。因此，它非常适合蛋白质搜索。我们的实验结果表明，它在寻找在 SCOP 家族和超家族水平上结构相似的蛋白质方面比其他著名的蛋白质搜索系统更准确，并且它的速度也具有竞争力。在两两比对性能方面，它与一些著名的比对算法一样好。
