The De Bruijn graph of non-sequential pattern repetitions in DNA strings

Abstract

In molecular biology, constructing a genome based on substantially many reads from multitudes of deoxyribonucleic acid (DNA) strings has become an insurmountable task; one which has been continuously addressed by the introduction of various assembly algorithms based on three steps called the overlap-layout-consensus strategy. In the overlap step, the De Bruijn graph is one of many graphs that illustrate the data of all the assembly algorithms. In this article, by using definitions and methods of mathematical induction, some properties of the De Bruijn graph of one time and two times non-sequential repetition of patterns in a DNA string are presented. Examples of these De Bruijn graphs are also given. From there, a generalisation of said properties for m times non-sequential pattern repetition in a DNA string is acquired by means of mathematical induction, as well. The theoretical work in this research is invaluable to develop algorithms that increase the computational efficiency of assembly algorithms.