Alignment of distantly related protein structures: algorithm, bound and implications to homology modeling

Abstract Motivation: Building an accurate alignment of a large set of distantly related protein structures is still very challenging. Results: This article presents a novel method 3DCOMB that can generate a multiple structure alignment (MSA) with not only as many conserved cores as possible, but also high-quality pairwise alignments. 3DCOMB is unique in that it makes use of both local and global structure environments, combined by a statistical learning method, to accurately identify highly similar fragment blocks (HSFBs) among all proteins to be aligned. By extending the alignments of these HSFBs, 3DCOMB can quickly generate an accurate MSA without using progressive alignment. 3DCOMB significantly excels others in aligning distantly related proteins. 3DCOMB can also generate correct alignments for functionally similar regions among proteins of very different structures while many other MSA tools fail. 3DCOMB is useful for many real-world applications. In particular, it enables us to find out that there is still large improvement room for multiple template homology modeling while several other MSA tools fail to do so. Availability: 3DCOMB is available at http://ttic.uchicago.edu/~jinbo/software.htm. Contact: jinboxu@gmail.com Supplementary Information: Supplementary data are available at Bioinformatics online.