An integer programming approach to DNA sequence assembly.

De novo sequence assembly is a ubiquitous combinatorial problem in all DNA sequencing technologies. In the presence of errors in the experimental data, the assembly problem is computationally challenging, and its solution may not lead to a unique reconstruct. The enumeration of all alternative solutions is important in drawing a reliable conclusion on the target sequence, and is often overlooked in the heuristic approaches that are currently available. In this paper, we develop an integer programming formulation and global optimization solution strategy to solve the sequence assembly problem with errors in the data. We also propose an efficient technique to identify all alternative reconstructs. When applied to examples of sequencing-by-hybridization, our approach dramatically increases the length of DNA sequences that can be handled with global optimality certificate to over 10,000, which is more than 10 times longer than previously reported. For some problem instances, alternative solutions exhibited a wide range of different ability in reproducing the target DNA sequence. Therefore, it is important to utilize the methodology proposed in this paper in order to obtain all alternative solutions to reliably infer the true reconstruct. These alternative solutions can be used to refine the obtained results and guide the design of further experiments to correctly reconstruct the target DNA sequence.

Identification of optimal measurement sets for complete flux elucidation in metabolic flux analysis experiments.

Metabolic flux analysis (MFA) methods use external flux and isotopic measurements to quantify the magnitude of metabolic flows in metabolic networks. A key question in this analysis is choosing a set of measurements that is capable of yielding a unique flux distribution (identifiability). In this article, we introduce an optimization-based framework that uses incidence structure analysis to determine the smallest (or most cost-effective) set of measurements leading to complete flux elucidation. This approach relies on an integer linear programming formulation OptMeas that allows for the measurement of external fluxes and the complete (or partial) enumeration of the isotope forms of metabolites without requiring any of these to be chosen in advance. We subsequently query and refine the measurement sets suggested by OptMeas for identifiability and optimality. OptMeas is first tested on small to medium-size demonstration examples. It is subsequently applied to a large-scale E. coli isotopomer mapping model with more than 17,000 isotopomers. A number of additional measurements are identified leading to maximum flux elucidation in an amorphadiene producing E. coli strain.