Bioinformatics Vol. 15 no. 11 1999
Pages 930-936
© 1999 Oxford University Press
A simple algorithm for detecting circular permutations in proteins
1 Faculty of Life Sciences, Bar-Ilan
University, Ramat-Gan, 52900, Israel
2 Department of Computer Science, Bar-Ilan
University,
3 College of Computing, Georgia Tech,
Atlanta, GA 30332-0280, USA
Motivation: Circular permutation of a protein is a genetic operation in which part of the C-terminal of the protein is moved to its N-terminal. Recently, it has been shown that proteins that undergo engineered circular permutations generally maintain their three dimensional structure and biological function. This observation raises the possibility that circular permutation has occured in Nature during evolution. In this scenario a protein underwent circular permutation into another protein, thereafter both proteins further diverged by standard genetic operations. To study this possibility one needs an efficient algorithm that for a given pair of proteins can detect the underlying event of circular permutations. A possible formal description of the question is: given two sequences, find a circular permutation of one of them under which the edit distance between the proteins is minimal. A naive algorithm might take time proportional to N3 or even N4, which is prohibitively slow for a large-scale survey. A sophisticated algorithm that runs in asymptotic time of N2 was recently suggested, but it is not practical for a large-scale survey.
Results: A simple and efficient algorithm that runs in time N2 is presented. The algorithm is based on duplicating one of the two sequences, and then performing a modified version of the standard dynamic programming algorithm. While the algorithm is not guaranteed to find the optimal results, we present data that indicate that in practice the algorithm performs very well.
Availability: A Fortran program that calculates the optimal edit distance under circular permutation is available upon request from the authors.
Contact: ron{at}biocom1.ls.biu.ac.il
CiteULike 
Connotea 
Del.icio.us What's this?
This article has been cited by other articles:
|
|
 |
|
  W.-C. Lo, C.-C. Lee, C.-Y. Lee, and P.-C. Lyu CPDB: a database of circular permutation in proteins Nucleic Acids Res., October 8, 2008; (2008) gkn679v1. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 J. Weiner 3rd, G. Thomas, and E. Bornberg-Bauer Rapid motif-based prediction of circular permutations in multi-domain proteins Bioinformatics, April 1, 2005; 21(7): 932 - 937. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
L. Chen, T. Zhou, and Y. Tang Protein structure alignment by deterministic annealing Bioinformatics, January 1, 2005; 21(1): 51 - 62. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 A. N. Arslan and O. Egecioglu Dynamic Programming Based Approximation Algorithms for Sequence Alignment with Constraints INFORMS Journal on Computing, January 1, 2004; 16(4): 441 - 458. [Abstract] [PDF]
|
|
|
|
 |
|
 J. Jung and B. Lee Circularly permuted proteins in the protein structure database Protein Sci., September 1, 2001; 10(9): 1881 - 1886. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 S. Uliel, A. Fliess, and R. Unger Naturally occurring circular permutations in proteins Protein Eng. Des. Sel., August 1, 2001; 14(8): 533 - 542. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
N. V. Grishin KH domain: one motif, two folds Nucleic Acids Res., February 1, 2001; 29(3): 638 - 643. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
A. Bahr, J. D. Thompson, J.-C. Thierry, and O. Poch BAliBASE (Benchmark Alignment dataBASE): enhancements for repeats, transmembrane sequences and circular permutations Nucleic Acids Res., January 1, 2001; 29(1): 323 - 326. [Abstract] [Full Text] [PDF]
|
|