Design of DNA fragment assembly using IWP method on application-specific integrated-circuit / Hasniliati Hassan

Nowadays, DNA sequence assembly is needed due to limitation with current sequence technology. Depending on the technology used, it can only read small pieces of base between 20 to 1000 bases. The short read fragments generated by DNA sequencing technology offer challenges in the assembly process because some of them contain sequencong errors, coming from various sizes, and contain lots of repeats and overlaps. Therefore, computation capability and requirement is increased in order to assemble large amounts of short read data that are generated by sequencing technology. In recent years, many software programs have been developed in order to improve the assembly process. The main focus is how to efficiently reconstruct full strands of DNA based on the pieces of data they are able to record at the lowest cost possible. Most assemblers nowadays are software-based which take a significant amount of time to execute. Hence, in this research a method is proposed to design the DNA sequence assembly accelerator. The method proposed is to design DNA assembly algorithms in Verilog HDL and implemented it in ASIC design flow. The key innovation is to implement DNA sequence assembly algorithms on ASIC to make it a synthesisable IP block. After reviewing various algorithms, it was decided to apply de Bruijn graphs and Eulerian circuits that are based on graph theory. A de Bruijn graph is a compact representation based of short words (k-mers). While the Eulerian paths that existing in the de Bruijn graph are represented as DNA sequence assembly outputs. This combination of both de Bruijn graph and Eulerian circuit is called the Idury Waterman Pevzner (IWP) Method. The IWP module was modelled and designed in Verilog HDL using Xilinx ISE Design Suite version 14.2. The implementation of design in ASIC was then done using Synopsys EDA tools. In this work, the main focus is to seek optimal solutions for DNA fragment assembly problems in terms of assembly accuracy. Simulation results showed that the IWP module in Verilog HDL can assemble short reads data efficiently same as in theory, besides eliminating repeats. Further analysis has been conducted on the IWP module in ASIC design flow in terms of assembly running time, power consumption and total area consumed. The results obtained are LVC clean, no DRC error, positive slack for both setup and hold time where 83.541ns and 0.097ns respectively. All these analyses were performed using industrial standards via Synopsys EDA tools which are VCS, DC and Astro.