Next Generation Sequencing (NGS) platforms are capable of rapidly generating a large number of short reads (40-400 base pairs). In order to take advantage of overlapping short reads, several sequencing algorithms are implemented on the basis of the Eulerian Path solution, which breaks up reads into fixed-size segments. By breaking up a read into several overlapping segments, it is contended that some information associated with a read is lost. In this work, we implement the resequencing and de novo sequencing approaches to DNA sequencing with the use of graph algorithms to improve the efficiency of overlapping reads and the use of all the reads. Instead of comparing a read to all other reads for possible overlap, we propose a strategically partitioning of the reads into buckets, minimize the bucket size and use resulting reads to build a graph, from which all possible contigs are generated.
展开▼
