Penyusunan Overlap Graph menggunakan Suffix Tree pada DNA Sequence

Abstract

The DNA sequence assembly is very important in genome analysis. This step aims to reconstruct contigous DNA fragment (contigs) from short fragment by concatenating fragments based on the overlap region among them. This method employs overlap graph for solving the problems. In this graph, nodes represent fragments and edges represent overlap. This research developed a software for constructing overlap graph using suffix tree. The evaluation was conducted by measuring the number of nodes, number of edges, and the execution time in many values of minimum overlap. The minimum overlap is defined as the minimum length of substring which is considered as the overlap region between two fragments. The evaluation results showed that the number of nodes, the number of edges, and the execution time were increased with the decreasing of the minimum overlap value.