Summary
International Symposium on Nonlinear Theory and its Applications
2010
Session Number:B3L-A
Session:
Number:B3L-A3
Heuristics Methods for Asymmetric Traveling Salesman Problem and Their Applications to DNA Fragment Assembly
Tomohiro Kato, Mikio Hasegawa,
pp.386-389
Publication Date:2010/9/5
Online ISSN:2188-5079
Summary:
A traveling salesman problem is a problem on which a salesman finds the shortest course that patrols N cities as a copy one time respectively. There are many examples of application in TSP, and it is a problem important also on practical use. In this paper, a DNA problem is studied as one of these application. The DNA fragment assembly problem consists in building the DNA sequence from several hundreds of fragments obtained by biologists in the laboratory. This DNA fragmentation joint problem hits the asymmetrical traveling salesman problem which extended TSP asymmetrically. We tried the heuristic solution on the asymmetric traveling salesman problem and solved the DNA fragment assembly problem by the solution.