A Grid-based TSP Solver with Applications to Bioinformatics

Abstract

Traveling salesperson problem (TSP for short) is a classic optimization problem. It finds a shortest cycle that contains each vertex exactly once. In Bioinformatics, it has been shown that there are many problems can be solved by solving the traveling salesperson problem, such as multiple sequence alignment, genome sequencing, physical mapping, DNA universal strings, evolutionary tree reconstruction, protein structure prediction, and so on. However, the TSP has been shown that it is an NP-hard problem. It is unlikely to be solved in polynomial time. In this paper, we implement a branch-and-bound algorithm on Grid environment for the traveling salesperson problem. It is called a TSP solver. Then we use it to solve the multiple sequence alignment problem which is a hard problem in Bioinformatics. The experiment shows that Grid computing is a powerful computing system and it has a better performance than a distributed system.