tailieunhanh - Báo cáo sinh học: " Linear-time protein 3-D structure searching with insertions and deletions"

Tuyển tập các báo cáo nghiên cứu về sinh học được đăng trên tạp chí y học Molecular Biology cung cấp cho các bạn kiến thức về ngành sinh học đề tài: Linear-time protein 3-D structure searching with insertions and deletions. | Shibuya et al. Algorithms for Molecular Biology 2010 5 7 http content 5 1 7 AMR ALGORITHMS FOR MOLECULAR BIOLOGY RESEARCH Open Access Linear-time protein 3-D structure searching with insertions and deletions Tetsuo Shibuya1 Jesper Jansson2 Kunihiko Sadakane3 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 . 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. Background It is widely known that biomolecules with similar 3-D structures tend to have similar functions and we can estimate molecular functions by searching for structurally similar molecules from 3-D structure