PubMed Health⌕ Search

Biomedical subjects

S Uliel

Publications and source records attributed to S Uliel.

3 recordsLinked to original sources
PubMed2001

Naturally occurring circular permutations in proteins.

A pair of proteins is defined to be related by a circular permutation if the N-terminal region of one protein has significant sequence similarity to the C-terminal of the other and vice versa. To detect pairs of proteins that might be related by circular permutation, we implemented a procedure based on a combination of a fast screening algorithm that we had designed and manual verification of candidate pairs. The screening algorithm is a variation of a dynamic programming string matching algorithm, in which one of the sequences is doubled. This algorithm, although not guaranteed to identify all cases of circular permutation, is a good first indicator of protein pairs related by permutation events. The candidate pairs were further validated first by application of an exhaustive string matching algorithm and then by manual inspection using the dotplot visual tool. Screening the whole Swissprot database, a total of 25 independent protein pairs were identified. These cases are presented here, divided into three categories depending on the level of functional similarity of the related proteins. To validate our approach and to confirm further the small number of circularly permuted protein pairs, a systematic search for cases of circular permutation was carried out in the Pfam database of protein domains. Even with this more inclusive definition of a circular permutation, only seven additional candidates were found. None of these fitted our original definition of circular permutations. The small number of cases of circular permutation suggests that there is no mechanism of local genetic manipulation that can induce circular permutations; most examples observed seem to result from fusion of functional units.

Algorithms↗
PubMed1999

A simple algorithm for detecting circular permutations in proteins.

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 occurred 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@biocom1.ls.biu.ac.il.

Algorithms↗