Related Experiment Videos
A simple algorithm for detecting circular permutations in proteins
Bioinformatics (Oxford, England)
|April 1, 2000
Summary
We present a simple and efficient N2 algorithm to detect circular permutation events in proteins, a potential evolutionary mechanism. This method aids in analyzing protein evolution by finding minimal edit distances between circularly permuted sequences.
Area of Science:
- Bioinformatics
- Computational Biology
- Evolutionary Biology
Background:
- Circular permutation, where a protein's C-terminus is moved to its N-terminus, can preserve structure and function.
- This suggests natural circular permutation may have occurred during protein evolution.
- Detecting such events requires efficient algorithms for large-scale sequence analysis.
Purpose of the Study:
- To develop an efficient algorithm for detecting circular permutation events in protein sequences.
- To identify pairs of proteins where one is a circular permutation of the other.
- To facilitate the study of natural circular permutation as an evolutionary mechanism.
Main Methods:
- A novel algorithm with N2 time complexity is presented.
- The method involves duplicating one sequence and applying a modified dynamic programming approach.
- This approach aims to find the minimal edit distance between circularly permuted protein sequences.
Main Results:
- An efficient N2 algorithm for detecting circular permutations is described.
- The algorithm's practical performance is shown to be very good, despite not guaranteeing optimality.
- A Fortran program is available for calculating optimal edit distances under circular permutation.
Conclusions:
- The developed algorithm offers a practical solution for identifying potential natural circular permutation events.
- This facilitates large-scale evolutionary studies of proteins.
- Further research can utilize this method to explore the role of circular permutation in protein evolution.