Source author record

Ming-Yang Kao

Ming-Yang Kao appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Data Structures and Algorithms Computational Complexity Discrete Mathematics Computational Engineering, Finance, and Science Information Theory math.IT Populations and Evolution

Catalog footprint

What is connected

5works

7topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2014arXiv

A manually-checkable proof for the NP-hardness of 11-color pattern self-assembly tile set synthesis

Patterned self-assembly tile set synthesis (PATS) aims at finding a minimum tile set to uniquely self-assemble a given rectangular (color) pattern. For k >= 1, k-PATS is a variant of PATS that restricts input patterns to those with at most $k$ colors. A computer-assisted proof has been recently proposed for 2-PATS by Kari et al. [arXiv:1404.0967 (2014)]. In contrast, the best known manually-checkable proof is for the NP-hardness of 29-PATS by Johnsen, Kao, and Seki [ISAAC 2013, LNCS 8283, pp.~699-710]. We propose a manually-checkable proof for the NP-hardness of 11-PATS.

preprint2014arXiv

Computing Minimum Tile Sets to Self-Assemble Colors Patterns

Patterned self-assembly tile set synthesis (PATS) aims at finding a minimum tile set to uniquely self-assemble a given rectangular color pattern. For $k \ge 1$, $k$-PATS is a variant of PATS that restricts input patterns to those with at most $k$ colors. We prove the {\bf NP}-hardness of 29-PATS, where the best known is that of 60-PATS.

preprint2012arXiv

Deterministic Polynomial-Time Algorithms for Designing Short DNA Words

Designing short DNA words is a problem of constructing a set (i.e., code) of n DNA strings (i.e., words) with the minimum length such that the Hamming distance between each pair of words is at least k and the n words satisfy a set of additional constraints. This problem has applications in, e.g., DNA self-assembly and DNA arrays. Previous works include those that extended results from coding theory to obtain bounds on code and word sizes for biologically motivated constraints and those that applied heuristic local searches, genetic algorithms, and randomized algorithms. In particular, Kao, Sanghi, and Schweller (2009) developed polynomial-time randomized algorithms to construct n DNA words of length within a multiplicative constant of the smallest possible word length (e.g., 9 max{log n, k}) that satisfy various sets of constraints with high probability. In this paper, we give deterministic polynomial-time algorithms to construct DNA words based on derandomization techniques. Our algorithms can construct n DNA words of shorter length (e.g., 2.1 log n + 6.28 k) and satisfy the same sets of constraints as the words constructed by the algorithms of Kao et al. Furthermore, we extend these new algorithms to construct words that satisfy a larger set of constraints for which the algorithms of Kao et al. do not work.

preprint2012arXiv

Optimizing Tile Concentrations to Minimize Errors and Time for DNA Tile Self-Assembly Systems

DNA tile self-assembly has emerged as a rich and promising primitive for nano-technology. This paper studies the problems of minimizing assembly time and error rate by changing the tile concentrations because changing the tile concentrations is easy to implement in actual lab experiments. We prove that setting the concentration of tile $T_i$ proportional to the square root of $N_i$ where $N_i$ is the number of times $T_i$ appears outside the seed structure in the final assembled shape minimizes the rate of growth errors for rectilinear tile systems. We also show that the same concentrations minimize the expected assembly time for a feasible class of tile systems. Moreover, for general tile systems, given tile concentrations, we can approximate the expected assembly time with high accuracy and probability by running only a polynomial number of simulations in the size of the target shape.

preprint2011arXiv

On Approximating Four Covering and Packing Problems

In this paper, we consider approximability issues of the following four problems: triangle packing, full sibling reconstruction, maximum profit coverage and 2-coverage. All of them are generalized or specialized versions of set-cover and have applications in biology ranging from full-sibling reconstructions in wild populations to biomolecular clusterings; however, as this paper shows, their approximability properties differ considerably. Our inapproximability constant for the triangle packing problem improves upon the previous results; this is done by directly transforming the inapproximability gap of Haastad for the problem of maximizing the number of satisfied equations for a set of equations over GF(2) and is interesting in its own right. Our approximability results on the full siblings reconstruction problems answers questions originally posed by Berger-Wolf et al. and our results on the maximum profit coverage problem provides almost matching upper and lower bounds on the approximation ratio, answering a question posed by Hassin and Or.