A Minimal Normal Form for DNA Expressions

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. [email protected]

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 define a (minimal) normal form for the language of DNA expressions, and describe an algorithm to rewrite a given DNA expression into the normal form.

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

DOI: 10.3233/FI-2012-808

Journal: Fundamenta Informaticae, vol. 123, no. 2, pp. 227-243, 2013