DocumentCode :
429471
Title :
Order independent structural alignment of circularly permuted proteins
Author :
Binkowski, T. Andrew ; DasGupta, Bhaskar ; Liang, Jie
Author_Institution :
Dept. of Bioeng., Illinois Univ., Chicago, IL, USA
Volume :
1
fYear :
2004
fDate :
1-5 Sept. 2004
Firstpage :
2781
Lastpage :
2784
Abstract :
Circular permutation connects the N and C termini of a protein and concurrently cleaves elsewhere in the chain, providing an important mechanism for generating novel protein fold and functions. However, their in genomes is unknown because current detection methods can miss many occurrences, mistaking random repeats as circular permutation. Here we develop a method for detecting circularly permuted proteins from structural comparison. Sequence order independent alignment of protein structures can be regarded as a special case of the maximum-weight independent set problem, which is known to be computationally hard. We develop an efficient approximation algorithm by repeatedly solving relaxations of an appropriate intermediate integer programming formulation, we show that the approximation ratio is much better than the theoretical worst case ratio of r=1/4. Circularly permuted proteins reported in literature can be identified rapidly with our method, while they escape the detection by publicly available servers for structural alignment.
Keywords :
approximation theory; biochemistry; biology computing; genetics; integer programming; linear programming; molecular biophysics; molecular configurations; proteins; C terminal; N terminal; approximation algorithm; approximation ratio; circularly permuted proteins; genomes; integer programming formulation; linear programming; protein fold; protein functions; protein sequence; protein structural alignment; protein structures; Approximation algorithms; Bioinformatics; Biomedical engineering; Concurrent computing; Genetic mutations; Genomics; Linear programming; Peptides; Proteins; Sequences; circular permuations; integer programming; linear programming; protein structure alignment;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Engineering in Medicine and Biology Society, 2004. IEMBS '04. 26th Annual International Conference of the IEEE
Conference_Location :
San Francisco, CA
Print_ISBN :
0-7803-8439-3
Type :
conf
DOI :
10.1109/IEMBS.2004.1403795
Filename :
1403795
Link To Document :
بازگشت