The De Bruijn graph of non-sequential pattern repetitions in DNA strings
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...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Institute of Advanced Engineering and Science
2024
|
| Subjects: | |
| Online Access: | http://eprints.utm.my/108986/1/WanHengFong2024_TheDeBruijnGraphofNonSequentialPatternRepetitions.pdf |
| _version_ | 1824452079370895360 |
|---|---|
| author | Fong, Wan Heng Ahmed Ildrussi, Ahmed Ildrussi Yosman, Ahmad Firdaus |
| author_facet | Fong, Wan Heng Ahmed Ildrussi, Ahmed Ildrussi Yosman, Ahmad Firdaus |
| author_sort | Fong, Wan Heng |
| collection | ePrints |
| description | 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. |
| first_indexed | 2025-02-19T02:44:49Z |
| format | Article |
| id | utm.eprints-108986 |
| institution | Universiti Teknologi Malaysia - ePrints |
| language | English |
| last_indexed | 2025-02-19T02:44:49Z |
| publishDate | 2024 |
| publisher | Institute of Advanced Engineering and Science |
| record_format | dspace |
| spelling | utm.eprints-1089862025-01-27T01:52:49Z http://eprints.utm.my/108986/ The De Bruijn graph of non-sequential pattern repetitions in DNA strings Fong, Wan Heng Ahmed Ildrussi, Ahmed Ildrussi Yosman, Ahmad Firdaus QA Mathematics 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. Institute of Advanced Engineering and Science 2024-08 Article PeerReviewed application/pdf en http://eprints.utm.my/108986/1/WanHengFong2024_TheDeBruijnGraphofNonSequentialPatternRepetitions.pdf Fong, Wan Heng and Ahmed Ildrussi, Ahmed Ildrussi and Yosman, Ahmad Firdaus (2024) The De Bruijn graph of non-sequential pattern repetitions in DNA strings. Indonesian Journal of Electrical Engineering and Computer Science, 35 (2). pp. 787-794. ISSN 2502-4752 http://dx.doi.org/10.11591/ijeecs.v35.i2.pp787-794 DOI:10.11591/ijeecs.v35.i2.pp787-794 |
| spellingShingle | QA Mathematics Fong, Wan Heng Ahmed Ildrussi, Ahmed Ildrussi Yosman, Ahmad Firdaus The De Bruijn graph of non-sequential pattern repetitions in DNA strings |
| title | The De Bruijn graph of non-sequential pattern repetitions in DNA strings |
| title_full | The De Bruijn graph of non-sequential pattern repetitions in DNA strings |
| title_fullStr | The De Bruijn graph of non-sequential pattern repetitions in DNA strings |
| title_full_unstemmed | The De Bruijn graph of non-sequential pattern repetitions in DNA strings |
| title_short | The De Bruijn graph of non-sequential pattern repetitions in DNA strings |
| title_sort | de bruijn graph of non sequential pattern repetitions in dna strings |
| topic | QA Mathematics |
| url | http://eprints.utm.my/108986/1/WanHengFong2024_TheDeBruijnGraphofNonSequentialPatternRepetitions.pdf |
| work_keys_str_mv | AT fongwanheng thedebruijngraphofnonsequentialpatternrepetitionsindnastrings AT ahmedildrussiahmedildrussi thedebruijngraphofnonsequentialpatternrepetitionsindnastrings AT yosmanahmadfirdaus thedebruijngraphofnonsequentialpatternrepetitionsindnastrings AT fongwanheng debruijngraphofnonsequentialpatternrepetitionsindnastrings AT ahmedildrussiahmedildrussi debruijngraphofnonsequentialpatternrepetitionsindnastrings AT yosmanahmadfirdaus debruijngraphofnonsequentialpatternrepetitionsindnastrings |