5 papers
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…
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.…
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…
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…
A Decomposition Theorem for Maximum Weight Bipartite Matchings
Ming-Yang Kao, Tak-Wah Lam, Wing-Kin Sung +1
Let G be a bipartite graph with positive integer weights on the edges and without isolated nodes. Let n, N and W be the node count, the largest edge weight and the total weight of…