Dynamic Programming Used to Align Protein Structures with a Spectrum is Robust

Overview

Journal Biology (Basel)

Publisher MDPI

Specialty Biology

Date 2014 May 17

PMID 24833226

Citations 2

Authors

Allen Holder

Jacqueline Simon

Jonathon Strauser

Jonathan Taylor

Yosi Shibberu

Affiliations

Soon will be listed here.

Abstract

Several efficient algorithms to conduct pairwise comparisons among large databases of protein structures have emerged in the recent literature. The central theme is the design of a measure between the Cα atoms of two protein chains, from which dynamic programming is used to compute an alignment. The efficiency and efficacy of these algorithms allows large-scale computational studies that would have been previously impractical. The computational study herein shows that the structural alignment algorithm eigen-decomposition alignment with the spectrum (EIGAs) is robust against both parametric and structural variation.

Citing Articles

SAFoldNet: A Novel Tool for Discovering and Aligning Three-Dimensional Protein Structures Based on a Neural Network.

Petrovskiy D, Nikolsky K, Rudnev V, Kulikova L, Butkova T, Malsagova K Int J Mol Sci. 2023; 24(19).

PMID: 37833886 PMC: 10572457. DOI: 10.3390/ijms241914439.

Comparative genomic analysis of the principal species that infect humans.

Arias-Agudelo L, Garcia-Montoya G, Cabarcas F, Galvan-Diaz A, Alzate J PeerJ. 2020; 8:e10478.

PMID: 33344091 PMC: 7718795. DOI: 10.7717/peerj.10478.

References

Lu Z, Zhao Z, Fu B . Efficient protein alignment algorithm for protein search. BMC Bioinformatics. 2010; 11 Suppl 1:S34. PMC: 3009506. DOI: 10.1186/1471-2105-11-S1-S34. View

Di Lena P, Fariselli P, Margara L, Vassura M, Casadio R . Fast overlapping of protein contact maps by alignment of eigenvectors. Bioinformatics. 2010; 26(18):2250-8. DOI: 10.1093/bioinformatics/btq402. View

Shibberu Y, Holder A . A spectral approach to protein structure alignment. IEEE/ACM Trans Comput Biol Bioinform. 2011; 8(4):867-75. DOI: 10.1109/TCBB.2011.24. View

Cock P, Antao T, Chang J, Chapman B, Cox C, Dalke A . Biopython: freely available Python tools for computational molecular biology and bioinformatics. Bioinformatics. 2009; 25(11):1422-3. PMC: 2682512. DOI: 10.1093/bioinformatics/btp163. View

Lo Conte L, Ailey B, Hubbard T, Brenner S, Murzin A, Chothia C . SCOP: a structural classification of proteins database. Nucleic Acids Res. 1999; 28(1):257-9. PMC: 102479. DOI: 10.1093/nar/28.1.257. View

Pang B, Zhao N, Becchi M, Korkin D, Shyu C . Accelerating large-scale protein structure alignments with graphics processing units. BMC Res Notes. 2012; 5:116. PMC: 3309952. DOI: 10.1186/1756-0500-5-116. View

Poleksic A . Algorithms for optimal protein structure alignment. Bioinformatics. 2009; 25(21):2751-6. DOI: 10.1093/bioinformatics/btp530. View

NEEDLEMAN S, Wunsch C . A general method applicable to the search for similarities in the amino acid sequence of two proteins. J Mol Biol. 1970; 48(3):443-53. DOI: 10.1016/0022-2836(70)90057-4. View

Liu W, Srivastava A, Zhang J . A mathematical framework for protein structure comparison. PLoS Comput Biol. 2011; 7(2):e1001075. PMC: 3033361. DOI: 10.1371/journal.pcbi.1001075. View

10.

Shindyalov I, Bourne P . Protein structure alignment by incremental combinatorial extension (CE) of the optimal path. Protein Eng. 1998; 11(9):739-47. DOI: 10.1093/protein/11.9.739. View

11.

Chen L, Wu L, Wang Y, Zhang S, Zhang X . Revealing divergent evolution, identifying circular permutations and detecting active-sites by protein structure comparison. BMC Struct Biol. 2006; 6:18. PMC: 1574323. DOI: 10.1186/1472-6807-6-18. View

12.

Bonnel N, Marteau P . LNA: fast protein structural comparison using a Laplacian characterization of tertiary structure. IEEE/ACM Trans Comput Biol Bioinform. 2012; 9(5):1451-8. DOI: 10.1109/TCBB.2012.64. View

13.

Kifer I, Nussinov R, Wolfson H . GOSSIP: a method for fast and accurate global alignment of protein structures. Bioinformatics. 2011; 27(7):925-32. PMC: 3065682. DOI: 10.1093/bioinformatics/btr044. View

14.

Madhusudhan M, Marti-Renom M, Sanchez R, Sali A . Variable gap penalty for protein sequence-structure alignment. Protein Eng Des Sel. 2006; 19(3):129-33. DOI: 10.1093/protein/gzj005. View

15.

Pascual-Garcia A, Abia D, Ortiz A, Bastolla U . Cross-over between discrete and continuous protein structure space: insights into automatic classification and networks of protein structures. PLoS Comput Biol. 2009; 5(3):e1000331. PMC: 2654728. DOI: 10.1371/journal.pcbi.1000331. View

16.

Ritchie D, Ghoorah A, Mavridis L, Venkatraman V . Fast protein structure alignment using Gaussian overlap scoring of backbone peptide fragment similarity. Bioinformatics. 2012; 28(24):3274-81. DOI: 10.1093/bioinformatics/bts618. View

17.

Novosad T, Snasel V, Abraham A, Yang J . Searching protein 3-D structures for optimal structure alignment using intelligent algorithms and data structures. IEEE Trans Inf Technol Biomed. 2010; 14(6):1378-86. DOI: 10.1109/TITB.2010.2079939. View

18.

Bhattacharya S, Bhattacharyya C, Chandra N . Projections for fast protein structure retrieval. BMC Bioinformatics. 2007; 7 Suppl 5:S5. PMC: 1764482. DOI: 10.1186/1471-2105-7-S5-S5. View

19.

Andonov R, Malod-Dognin N, Yanev N . Maximum contact map overlap revisited. J Comput Biol. 2011; 18(1):27-41. DOI: 10.1089/cmb.2009.0196. View

20.

Shibuya T, Jansson J, Sadakane K . Linear-time protein 3-D structure searching with insertions and deletions. Algorithms Mol Biol. 2010; 5:7. PMC: 2830924. DOI: 10.1186/1748-7188-5-7. View