Difference between revisions of "Open Problems:61"
(Created page with "{{Header |title=RNA Folding |source=bertinoro14 |who=Qin Zhang }} ???") |
|||
| Line 4: | Line 4: | ||
|who=Qin Zhang | |who=Qin Zhang | ||
}} | }} | ||
| − | + | ||
| + | An RNA sequence is a string of letters from the alphabet {A, C, G, U}, where A-U and C-G form pairings. A set of pairings in such a string is said to be non-crossing if there are no pairs of the form $(i, j), (k, l)$ where $i < k < j$. | ||
| + | |||
| + | A maximum non-crossing matching is a pairing of A-U and C-G of maximum cardinality that is non-crossing. Given a string, such a matching can be computed in $n^2$ space and $n^3$ time via dynamic programming. | ||
| + | |||
| + | Note that there is a trivial 2-approximation to the optimal matching. Find the optimal matchings on the A, U and C, G subsequences, and take the larger one. This can be computed in a stream. | ||
| + | |||
| + | Is there a streaming algorithm that yields a factor better than 2 ? | ||
Revision as of 17:21, 28 May 2014
| Suggested by | Qin Zhang |
|---|---|
| Source | Bertinoro 2014 |
| Short link | https://sublinear.info/61 |
An RNA sequence is a string of letters from the alphabet {A, C, G, U}, where A-U and C-G form pairings. A set of pairings in such a string is said to be non-crossing if there are no pairs of the form $(i, j), (k, l)$ where $i < k < j$.
A maximum non-crossing matching is a pairing of A-U and C-G of maximum cardinality that is non-crossing. Given a string, such a matching can be computed in $n^2$ space and $n^3$ time via dynamic programming.
Note that there is a trivial 2-approximation to the optimal matching. Find the optimal matchings on the A, U and C, G subsequences, and take the larger one. This can be computed in a stream.
Is there a streaming algorithm that yields a factor better than 2 ?
