Showing 2001Show all
3 papers · 1 filter
cs.CE2001
Predicting RNA Secondary Structures with Arbitrary Pseudoknots by Maximizing the Number of Stacking Pairs
Samuel Ieong, Ming-Yang Kao, Tak-Wah Lam +2
The paper investigates the computational problem of predicting RNA secondary structures. The general belief is that allowing pseudoknots makes the problem hard. Existing polynomial…
cs.CE2001
Cavity Matchings, Label Compressions, and Unrooted Evolutionary Trees
Ming-Yang Kao, Tak-Wah Lam, Wing-Kin Sung +1
We present an algorithm for computing a maximum agreement subtree of two unrooted evolutionary trees. It takes O(n^{1.5} log n) time for trees with unbounded degrees, matching the…
cs.CV2001
An Even Faster and More Unifying Algorithm for Comparing Trees via Unbalanced Bipartite Matchings
Ming-Yang Kao, Tak-Wah Lam, Wing-Kin Sung +1
A widely used method for determining the similarity of two labeled trees is to compute a maximum agreement subtree of the two trees. Previous work on this similarity measure is onl…