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

Wan Heng Fong, Ahmed Ildrussi, Ahmad Firdaus Yosman

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.

Keywords


De Bruijn; DNA; Graphs; Non-sequential; Repititions

Full Text:

PDF


DOI: http://doi.org/10.11591/ijeecs.v35.i2.pp787-794

Refbacks

  • There are currently no refbacks.


Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

Indonesian Journal of Electrical Engineering and Computer Science (IJEECS)
p-ISSN: 2502-4752, e-ISSN: 2502-4760
This journal is published by the Institute of Advanced Engineering and Science (IAES) in collaboration with Intelektual Pustaka Media Utama (IPMU).

shopify stats IJEECS visitor statistics