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

Tetsuo Shibuya, Jesper Andreas Jansson, Kunihiko Sadakane

Research output: Journal article publicationJournal articleAcademic researchpeer-review

10 Citations (Scopus)


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.
Original languageEnglish
Article number7
JournalAlgorithms for Molecular Biology
Issue number1
Publication statusPublished - 4 Jan 2010
Externally publishedYes

ASJC Scopus subject areas

  • Structural Biology
  • Molecular Biology
  • Computational Theory and Mathematics
  • Applied Mathematics


Dive into the research topics of 'Linear-time protein 3-D structure searching with insertions and deletions'. Together they form a unique fingerprint.

Cite this