Academic Journals Database
Disseminating quality controlled scientific knowledge

Linear-time protein 3-D structure searching with insertions and deletions

ADD TO MY LIST
 
Author(s): Shibuya Tetsuo | Jansson Jesper | Sadakane Kunihiko

Journal: Algorithms for Molecular Biology
ISSN 1748-7188

Volume: 5;
Issue: 1;
Start page: 7;
Date: 2010;
Original page

ABSTRACT
Abstract Background Two biomolecular 3-D structures are said to be similar if the RMSD (root mean square deviation) between the two molecules' sequences of 3-D coordinates is less than or equal to some given constant bound. Tools for searching for similar structures in biomolecular 3-D structure databases are becoming increasingly important in the structural biology of the post-genomic era. Results We consider an important, fundamental problem of reporting all substructures in a 3-D structure database of chain molecules (such as proteins) which are similar to a given query 3-D structure, with consideration of indels (i.e., insertions and deletions). This problem has been believed to be very difficult but its exact computational complexity has not been known. In this paper, we first prove that the problem in unbounded dimensions is NP-hard. We then propose a new algorithm that dramatically improves the average-case time complexity of the problem in 3-D in case the number of indels k is bounded by a constant. Our algorithm solves the above problem for a query of size m and a database of size N in average-case O(N) time, whereas the time complexity of the previously best algorithm was O(Nmk+1). Conclusions Our results show that although the problem of searching for similar structures in a database based on the RMSD measure with indels is NP-hard in the case of unbounded dimensions, it can be solved in 3-D by a simple average-case linear time algorithm when the number of indels is bounded by a constant.
Why do you need a reservation system?      Affiliate Program