Abstract
This paper proposes a parameterized algorithm for aligning two protein structures, in the case where one protein structure is represented by a contact map graph and the other by a contact map graph or a distance matrix. If the sequential order of alignment is not required, the time complexity is polynomial in the protein size and exponential with respect to two parameters \(\frac{D_u}{D_l}\) and \(\frac{D_c}{D_l}\), which usually can be treated as constants. In particular, D u is the distance threshold determining if two residues are in contact or not, D c is the maximally allowed distance between two matched residues after two proteins are superimposed, and D l is the minimum inter-residue distance in a typical protein. This result indicates that if both \(\frac{D_u}{D_l}\) and \(\frac{D_c}{D_l}\) are small enough, then there is a polynomial-time approximation scheme for the non-sequential protein structure alignment problem. Empirically, both \(\frac{D_u}{D_l}\) and \(\frac{D_c}{D_l}\) are very small and can be treated as constants. This result clearly demonstrates that the hardness of the contact-map based protein structure alignment problem is related not to protein size but to several parameters, which depend on how the protein structure alignment problem is modeled. The result is achieved by decomposing the protein structure using tree decomposition and discretizing the rigid-body transformation space. We have implemented our algorithm and preliminary experimental results indicate that on a Linux PC, it takes from ten minutes to one hour to align two proteins with approximately 100 residues.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Comin, M., Guerra, C., Zanotti, G.: PROuST: a comparison method of three-dimensional structures of proteins using indexing techniques. Journal of Computational Biology 11(6), 1061–1072 (2004)
Holm, L., Sander, C.: Protein structure comparison by alignment of distance matrices. Journal of Molecular Biology 233, 123–138 (1993)
Alexandrov, N.N.: SARFing the PDB. Protein Engineering 9, 727–732 (1996)
Gerstein, M., Levitt, M.: Using iterative dynamic programming to obtain accurate pairwise and multiple alignments of protein structures. In: Proceedings of International Conference on Intelligent Systems in Molecular Biology, pp. 59–67 (1996)
Singh, A.P., Brutlag, D.L.: Hierarchical protein structure superposition using both secondary structure and atomic representations. In: Proceedings of International Conference on Intelligent Systems in Molecular Biology, pp. 284–293 (1997)
Gibrat, J.F., Madej, T., Bryant, S.H.: Surprising similarities in structure comparison. Current Opinion in Structural Biology (6), 377–385 (1996)
Akutsu, T., Tashimo, H.: Protein structure comparison using representation by line segment sequences. In: Proceedings of Pacific Symposium on Biocomputing 1996 (PSB 1996), pp. 25–40 (1996)
Lancia, G., Carr, R., Walenz, B., Istrail, S.: 101 optimal PDB structure alignments: a branch-and-cut algorithm for the maximum contact map overlap problem. In: RECOMB 2001, pp. 193–202. ACM Press, New York (2001)
Caprara, A., Lancia, G.: Structural alignment of large–size proteins via Lagrangian relaxation. In: RECOMB 2002, pp. 100–108. ACM Press, New York (2002)
Lancia, G., Istrail, S.: Protein structure comparison: Algorithms and applications. In: Guerra, C., Istrail, S. (eds.) Mathematical Methods for Protein Structure Analysis and Design. LNCS (LNBI), vol. 2666, pp. 1–33. Springer, Heidelberg (2003)
Lemmen, C., Lengauer, T.: Computational methods for the structural alignment of molecules. Journal of Computer-Aided Molecular Design 14, 215–232 (2000)
Kolodny, R., Linial, N.: Approximate protein structural alignment in polynomial time. PNAS 101(33), 12201–12206 (2004)
Goldman, D., Papadimitriou, C.H., Istrail, S.: Algorithmic aspects of protein structure similarity. In: FOCS 1999: Proceedings of the 40th Annual Symposium on Foundations of Computer Science, pp. 512–522. IEEE Computer Society, Los Alamitos (1999)
Shindyalov, I.N., Bourne, P.E.: Protein structure alignment by incremental combinatorial extension (CE) of the optimal path. Protein Engineering 11(9), 739–747 (1998)
Verbitsky, O.: On the largest common subgraph problem (1994) (unpublished manuscript)
Jokisch, S., Müller, H.: Inter-point-distance-dependent approximate point set matching. Technical Report Research Report No. 653 (1997)
Yuan, X., Bystroff, C.: Non-sequential structure-based alignments reveal topology-independent core packing arrangements in proteins. Bioinformatics 27, 1010–1019 (2005)
Dror, O., Benyamini, H., Nussinov, R., Wolfson, H.: MASS: Multiple structural alignment by secondary structures. Bioinformatics 19(Suppl. 1), 95–104 (2003)
Zhu, J., Weng, Z.: FAST: A novel protein structure alignment algorithm. Proteins: Structure Function, and Bioinformatics (in Press, 2004)
Berman, H.M., Westbrook, J., Feng, Z., Gilliland, G., Bhat, T.N., Weissig, H., Shindyalov, I.N., Bourne, P.E.: The protein data bank. Nucleic Acids Research 28, 235–242 (2000)
Arun, K.S., Huang, T.S., Blostein, S.D.: Least-square fitting of two 3-d point sets. IEEE Trans. on Pattern Analysis and Machine Intelligence 9(5), 698–700 (1987)
Robertson, N., Seymour, P.D.: Graph minors. II. algorithmic aspects of tree-width. Journal of Algorithms 7, 309–322 (1986)
Xu, J.: Rapid side-chain packing via tree decomposition. In: Miyano, S., Mesirov, J., Kasif, S., Istrail, S., Pevzner, P.A., Waterman, M. (eds.) RECOMB 2005. LNCS (LNBI), vol. 3500, pp. 423–439. Springer, Heidelberg (2005)
Hao, M.H., Rackovsky, S., Liwo, A., Pincus, M.R., Scheraga, H.A.: Proc. Natl. Acad. Sci. USA 89, 6614–6618 (1992)
Caprara, A., Carr, R., Istrail, S., Lancia, G., Walenz, B.: 101 optimal PDB structure alignments: a branch-and-cut algorithm for the maximum contact map overlap problem. Journal of Computational Biology 11(1), 27–52 (2004)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Xu, J., Jiao, F., Berger, B. (2006). A Parameterized Algorithm for Protein Structure Alignment. In: Apostolico, A., Guerra, C., Istrail, S., Pevzner, P.A., Waterman, M. (eds) Research in Computational Molecular Biology. RECOMB 2006. Lecture Notes in Computer Science(), vol 3909. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11732990_41
Download citation
DOI: https://doi.org/10.1007/11732990_41
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-33295-4
Online ISBN: 978-3-540-33296-1
eBook Packages: Computer ScienceComputer Science (R0)