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: A simple, practical and complete O -time Algorithm for RNA folding using the FourRussians Speedup. | Frid and Gusfield Algorithms for Molecular Biology 2010 5 13 http content 5 1 13 AMR ALGORITHMS FOR MOLECULAR BIOLOGY RESEARCH Open Access A simple practical and complete O ĩỂ -time Algorithm for RNA folding using the Four-Russians Speedup Yelena Frid Dan Gusfield Abstract Background The problem of computationally predicting the secondary structure or folding of RNA molecules was first introduced more than thirty years ago and yet continues to be an area of active research and development. The basic RNA-folding problem of finding a maximum cardinality non-crossing matching of complimentary nucleotides in an RNA sequence of length n has an O n3 -time dynamic programming solution that is widely applied. It is known that an o n3 worst-case time solution is possible but the published and suggested methods are complex and have not been established to be practical. Significant practical improvements to the original dynamic programming method have been introduced but they retain the O n3 worst-case time bound when n is the only problem-parameter used in the bound. Surprisingly the most widely-used general technique to achieve a worst-case and often practical speed up of dynamic programming the Four-Russians technique has not been previously applied to the RNA-folding problem. This is perhaps due to technical issues in adapting the technique to RNA-folding. Results In this paper we give a simple complete and practical Four-Russians algorithm for the basic RNA-folding problem achieving a worst-case time-bound of O n3 log n . Conclusions We show that this time-bound can also be obtained for richer nucleotide matching scoring-schemes and that the method achieves consistent speed-ups in practice. The contribution is both theoretical and practical since the basic RNA-folding problem is often solved multiple times in the inner-loop of more complex algorithms and for long RNA molecules in the study of RNA virus genomes. Background The problem of computationally .
