Difference between revisions of "Open Problems:61"

From Open Problems in Sublinear Algorithms
Jump to: navigation, search
Line 5: Line 5:
 
}}
 
}}
  
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$.  
+
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 < l$.  
  
 
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.  
 
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.  
Line 11: Line 11:
 
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.  
 
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 ?
+
Is there a streaming algorithm that yields a factor better than 2 (in a small number of passes)?

Revision as of 12:00, 1 June 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 < l$.

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 (in a small number of passes)?