Algorithms For Fast Protein Structure Database Search And Multiple Protein Structure Alignment

With the rapid increase of the number of protein structures in the Protein Data Bank,it becomes urgent to develop efficient algorithms for protein structure comparisons.In this article,we present the mTM-align server for efficient protein structure comparisons.The server consists of two closely related modules: one for fast structure database searching and the other for multiple structure alignment.The database searching is speeded up based on a heuristic algorithm and a hierarchical organization of the structures in the database.Benchmark tests demonstrate that our algorithms outperform other peering methods such as Dali Server,in terms of speed and accuracy.The multiple structure alignment is an extension of the highly efficient pairwise structure alignment program TM-align.The algorithm was benchmarked on four widely used datasets,HOMSTRAD,SABmark_sup,SABmark_twi and SISY-multiple,showing that mTM-align consistently outperforms other algorithms.One of the unique features for the server is the interplay between database searching and multiple structure alignment.The server provides service not only for performing fast database searching,but also for making accurate multiple structure alignment with the structures found by the searching.In general,it takes about 2-5 minutes to complete the database searching for a structure of a medium size(~300 residues).For the multiple structure alignment,it takes a few seconds to complete for the input with ~10 structures of medium sizes.The server is freely available at: http://yanglab.nankai.edu.cn/mTM-align/.