PubMed Health⌕ Search

Biomedical subjects

Ion I Măndoiu

Publications and source records attributed to Ion I Măndoiu.

2 recordsLinked to original sources
PubMed2006

Exact and approximation algorithms for DNA tag set design.

In this paper, we propose new solution methods for designing tag sets for use in universal DNA arrays. First, we give integer linear programming formulations for two previous formalizations of the tag set design problem. We show that these formulations can be solved to optimality for problem instances of moderate size by using general purpose optimization packages and also give more scalable algorithms based on an approximation scheme for packing linear programs. Second, we note the benefits of periodic tags and establish an interesting connection between the tag design problem and the problem of packing the maximum number of vertex-disjoint directed cycles in a given graph. We show that combining a simple greedy cycle packing algorithm with a previously proposed alphabetic tree search strategy yields an increase of over 40% in the number of tags compared to previous methods.

Algorithms↗
PubMed2004

Scalable heuristics for design of DNA probe arrays.

Design of DNA arrays for very large-scale immobilized polymer synthesis (VLSIPS) (Fodor et al., 1991) seeks to minimize effects of unintended illumination during mask exposure steps. Hannenhalli et al. (2002) formulate this requirement as the Border Minimization Problem and give an algorithm for placement of probes at array sites under the assumption that the array synthesis is synchronous; i.e., nucleotides are synthesized in a periodic sequence (ACGT)(k) and every probe grows by exactly one nucleotide with every group of four masks. Drawing on the analogy with VLSI placement, in this paper we describe and experimentally validate the engineering of several scalable, high-quality placement heuristics for both synchronous and asynchronous DNA array design. We give empirical results on both randomly generated and industry test cases confirming the scalability and improved solution quality enjoyed by our methods. In general, our techniques improve on state-of-the-art industrial results by over 4% and surpass academically published results by up to 35%. Finally, we give lower bounds that offer insights into the amount of available further improvements.

Algorithms↗