Basic principles of the traveling salesman problem and radiation hybrid mapping
T.D. Vos · Research Repository (Delft University of Technology) · 2016
Every biological aspect of a create is described in the DNA. The DNA consists of very long strings that contain every biological information. Because these strings are very long, finding the right piece of information is a tough job. Fortunately, we have developed multiple ways to do this more quickly. Radiation hybrid mapping is such a method, it creates a map that shows us the locations of some essential pieces of information. We create a map with the help of the traveling salesman problem. The traveling salesman problem is a mathematical way to describe the desire to find tour through a set of places of minimal costs. The problem is not easy to solve, but many methods have been developed to make the search for the optimal solution easier. Dantzig, Fulkerson and Johnson constructed a combination of algorithms that solves the traveling salesman problem quickly in most practical efforts. With their technique we can construct the radiation hybrid map. Finally, there are many factors that determine the success rate of the map. With the right adjustments, we can create some large maps with a fairly good success rate, but doing so appears to be quiet difficult.