Bio-Inspired Models of Network, Information, and Computing Systems. 5th International ICST Conference, BIONETICS 2010, Boston, USA, December 1-3, 2010, Revised Selected Papers

Research Article

Protein Structure Alignment in Subquadratic Time

Download
525 downloads
  • @INPROCEEDINGS{10.1007/978-3-642-32615-8_36,
        author={Aleksandar Poleksic},
        title={Protein Structure Alignment in Subquadratic Time},
        proceedings={Bio-Inspired Models of Network, Information, and Computing Systems. 5th International ICST Conference, BIONETICS 2010, Boston, USA, December 1-3, 2010, Revised Selected Papers},
        proceedings_a={BIONETICS},
        year={2012},
        month={10},
        keywords={protein structure structure comparison alignment dynamic programming},
        doi={10.1007/978-3-642-32615-8_36}
    }
    
  • Aleksandar Poleksic
    Year: 2012
    Protein Structure Alignment in Subquadratic Time
    BIONETICS
    Springer
    DOI: 10.1007/978-3-642-32615-8_36
Aleksandar Poleksic1
  • 1: University of Northern Iowa Cedar Falls

Abstract

The problem of finding an optimal structural alignment for a pair of superimposed proteins is often amenable to the Smith-Waterman dynamic programming algorithm, which runs in time proportional to the product of the lengths of sequences being aligned. While the quadratic running time is acceptable for computing a single alignment of two, spatially “fixed”, structures, the time complexity becomes a bottleneck when running the Smith-Waterman routine multiple times in order to find an optimal pairwise superposition. We present a subquadratic running time algorithm capable of computing an alignment that optimizes one of the most widely used measures of protein structure similarity, defined as the number of pairs of residues in two proteins that can be superimposed under a predefined distance cutoff. The algorithm presented in this article can be used to significantly improve the speed-accuracy tradeoff in a number of popular protein structure alignment methods.