Simultaneous alignment and folding of protein sequences.
Accurate comparative analysis tools for low-homology proteins remains a difficult challenge in computational biology, especially sequence alignment and consensus folding problems. We present partiFold-Align, the first algorithm for simultaneous alignment and consensus folding of unaligned protein sequences; the algorithm's complexity is polynomial in time and space. Algorithmically, partiFold-Align exploits sparsity in the set of super-secondary structure pairings and alignment candidates to achieve an effectively cubic running time for simultaneous pairwise alignment and folding. We demonstrate the efficacy of these techniques on transmembrane β-barrel proteins, an important yet difficult class of proteins with few known three-dimensional structures. Testing against structurally derived sequence alignments, partiFold-Align significantly outperforms state-of-the-art pairwise and multiple sequence alignment tools in the most difficult low-sequence homology case. It also improves secondary structure prediction where current approaches fail. Importantly, partiFold-Align requires no prior training. These general techniques are widely applicable to many more protein families (partiFold-Align is available at http://partifold.csail.mit.edu/ ).
1 School of Computer Science, McGill University , Montreal, Canada .
Jérôme
J
Waldispühl
Charles W
CW
O'Donnell
Sebastian
S
Will
Srinivas
S
Devadas
Rolf
R
Backofen
Bonnie
B
Berger
D000465:Algorithms; D019295:Computational Biology; D006801:Humans; D008565:Membrane Proteins / Q000737:chemistry*; D008958:Models, Molecular; D017510:Protein Folding; D017433:Protein Structure, Secondary; D016415:Sequence Alignment; D012984:Software
D008565:Membrane Proteins