Exhaustive Search Meets DNA Sequencing: A Comprehensive Review of TSP-Based Approaches - Impana G.B.; Pallavi M. Jhadav; Mohammad Raffi (International Journal of Bioinformatics and Computational Biology, 2024)
Exhaustive search is a highly computational complex algorithm that checks every possibility to obtain the best solution. We illustrate an exhaustive search by applying it to three important problems: the traveling salesman problem, the knapsack problem, and the assignment problem. In this paper, we took a traveling salesman problem to explain DNA Sequencing. Since traveling salesman problem is an algorithmic problem that finds the shortest route between a set of points or locations that must be visited. Traveling salesman problem can be used to solve DNA sequencing problems by applying DNA computing. DNA sequencing is a crucial process in modern genetics. Traditional methods are often time-consuming and computationally expensive. This study proposes a novel approach to DNA sequencing by framing the problem as a traveling salesman problem. By leveraging efficient traveling salesman problem solvers, we reconstruct the original DNA sequence from fragmented reads. Our approach, traveling salesman problem-Seq, models the DNA sequencing problem as a weighted graph, where nodes represent reads and edges represent overlap between reads. The traveling salesman problem solver finds the shortest Hamiltonian cycle, corresponding to the most likely DNA sequence. We demonstrate the traveling salesman problem-Seq’s effectiveness on simulated and real-world datasets.
Keywords: DNA sequencing; Gene therapy; ant colony algorithm; organ transplant; travelling salesman problem