Showing cs.CEShow 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
The Enhanced Double Digest Problem for DNA Physical Mapping
Ming-Yang Kao, Jared Samet, Wing-Kin Sung
The double digest problem is a common NP-hard approach to constructing physical maps of DNA sequences. This paper presents a new approach called the enhanced double digest problem.…
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…