On some properties of DNA graphs

Molecular biology which aims to study DNA and protein structure and functio ns, has stimulated research in different scientific disciplines, discrete m athematics being one of them. One of the problems considered is that of rec ognition of DNA primary structure. It is known that some methods for solvin g this problem may be reduced (in their computational part) to graph-theore tic problems involving labeled graphs. Each vertex in such graphs has a lab el of length k written with an alphabet of size alpha, where k and alpha ar e two parameters. This paper is concerned with studying propel ties of thes e graphs (referred to as DNA graphs). More precisely, we give recognition a lgorithms and compare graphs labeled with different values of k and alpha. (C) 1999 Elsevier Science B.V. All rights reserved.