Open Problems:61 - Revision history

Krzysztof Onak at 22:55, 13 June 2014

2014-06-13T22:55:01Z

Krzysztof Onak: Krzysztof Onak moved page Waiting:Qin Zhang to Open Problems:61

2014-06-13T22:53:45Z

Krzysztof Onak moved page Waiting:Qin Zhang to Open Problems:61

Krzysztof Onak at 04:11, 4 June 2014

2014-06-04T04:11:04Z

Krzysztof Onak at 04:01, 4 June 2014

2014-06-04T04:01:18Z

Krzysztof Onak at 12:07, 1 June 2014

2014-06-01T12:07:59Z

Krzysztof Onak at 12:07, 1 June 2014

2014-06-01T12:07:02Z

Krzysztof Onak at 12:06, 1 June 2014

2014-06-01T12:06:37Z

Krzysztof Onak at 12:06, 1 June 2014

2014-06-01T12:06:02Z

Krzysztof Onak at 12:00, 1 June 2014

2014-06-01T12:00:08Z

Geomblog at 17:21, 28 May 2014

2014-05-28T17:21:38Z

@@ Line 1: / Line 1: @@
 {{Header
 |source=bertinoro14
 |who=Qin Zhang
 }}
 An RNA sequence is a string of letters from the alphabet $\{\mbox{A}, \mbox{C}, \mbox{G}, \mbox{U}\}$, where $\mbox{A---U}$ and $\mbox{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)$ and $(k, l)$, where $i < k < j < l$.

← Older revision		Revision as of 04:11, 4 June 2014
Line 12:		Line 12:

	How well can the size of the optimal non-crossing matching be approximated in $\operatorname{polylog}(n)$ space and a small number of passes?		How well can the size of the optimal non-crossing matching be approximated in $\operatorname{polylog}(n)$ space and a small number of passes?
		+
		+	(Additional question from Alex Andoni: Can the problem be solved in the RAM model with running time better than the trivial dynamic programming?)

@@ 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)$ and $(k, l)$, where $i < k < j < l$.
+An RNA sequence is a string of letters from the alphabet $\{\mbox{A}, \mbox{C}, \mbox{G}, \mbox{U}\}$, where $\mbox{A---U}$ and $\mbox{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)$ and $(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 $O(n^2)$ space and $O(n^3)$ time via dynamic programming {{cite|Eddy-04}}.
+A ''maximum non-crossing matching'' is a pairing of $\mbox{A---U}$ and $\mbox{C---G}$ of maximum cardinality that is non-crossing. Given a string of length $n$, such a matching can be computed in $O(n^2)$ space and $O(n^3)$ time via dynamic programming {{cite|Eddy-04}}.
-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 $\{\mbox{A}, \mbox{U}\}$ and $\{\mbox{C}, \mbox{G}\}$ subsequences, and take the larger one. In particular, this implies that a 2-approximation to the ''size'' of the optimal non-crossing matching can be computed in $O(1)$ space.
-Is there a streaming algorithm that yields a factor better than 2 (in a small number of passes)?
+How well can the size of the optimal non-crossing matching be approximated in $\operatorname{polylog}(n)$ space and a small number of passes?

@@ Line 7: / Line 7: @@
 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)$ and $(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 {{cite|Eddy-04}}.
+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 $O(n^2)$ space and $O(n^3)$ time via dynamic programming {{cite|Eddy-04}}.
 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)?

@@ 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)$ and $(k, l)$ where $i < k < j < l$.
+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)$ and $(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 {{cite|Eddy-04}}.

← Older revision	Revision as of 22:53, 13 June 2014
(No difference)

@@ 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.
@@ 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.
-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)?