• Calendar

June 10, Wednesday
12:00 – 13:30

Predicting secondary structures of RNA molecules is a classic example of a biological problem which is solved via the usage of computational tools. The original algorithms for the RNA folding problem (dating back to the late 70's) solve it in O(n^3) time and O(n^2) space complexities (where n denotes the length of the input sequence, and can get up to several hundreds). While these complexities are reasonable for the processing of a single input, they are inadequate for modern analysis of genome-wide data, which may include several billions of input sequences. Recently, the running time was improved to O(nZ), where Z is a sparsity parameter that satisfies n < Z < n^2. In the talk, new results will be presented, which reduce the space complexity to O(Z), and the time complexity to O(LZ), where L is a sparsity parameter that satisfies L < n. The presented techniques extend to a family of RNA folding algorithms, which include more sophisticated problem variants with higher time and space complexities, as well as to algorithms from other fields, such as parsing sentences with a given probabilistic context free grammar.