Making DNA Expressions Minimal

Article type: Research Article

Authors: van Vliet, Rudy | Hoogeboom, Hendrik Jan

Affiliations: Leiden Institute of Advanced Computer Science, Leiden University, Niels Bohrweg 1, 2333 CA Leiden, The Netherlands. rvvliet@liacs.nl

Note: [] Address for correspondence: Leiden Institute of Advanced Computer Science, Leiden University, Niels Bohrweg 1, 2333 CA Leiden, The Netherlands

Abstract: DNA expressions constitute a formal notation for DNA molecules that may contain nicks and gaps. Different DNA expressions may denote the same DNA molecule. We describe an algorithm to rewrite a given DNA expression into a DNA expression of minimal length denoting the same molecule.

Keywords: DNA molecules, formal notation, minimal DNA expressions, algorithm, complexity

DOI: 10.3233/FI-2012-807

Journal: Fundamenta Informaticae, vol. 123, no. 2, pp. 199-226, 2013