Design and Analysis of DNA Fragment Assembly's Converter and Checker Modules using De Bruijin Graph

摘要

This paper presents the Design and Analysis of DNA Fragment Assembly's Converter and Checker Modules using De Bruijin Graph. There are several objectives of this paper. The first objective is to design and analyze edges and vertices converter. Secondly, this paper will also discuss about designing and analyzing common edge and branch checker. In addition, all the modules will be integrated in one top module. Lastly, the integrated module will be simulated in Xilinx ISE software. Based on the objectives, this paper will discuss on constructing a DNA Fragment Assembly module that consist of four submodules which is Edges Converter, Vertices Converter, Common Edge Checker and Branch Checker. The sequencing method used in this paper is Hybridization method. Hybridization method is an option to shotgun sequencing. Hybridization uses the array identifying algorithm to identify the sequence. The algorithm used to construct the module is Bruijn Graph. De Bruijn Graph represents sequences of symbols from an alphabet, and edges that indicate where the sequence may overlap. First, the set of DNA will inserted in to the module, and then the module will do all the converting and checking process of the input before produce the output of vertices and the branch of edges. The entire algorithm and theory then been simulated in Xilinx to test the functionality.