The data used for the construction of genome maps is imperfect, therefore the
mapping of a physically linear structure must take place in a very uneven feature space.
As the number of genes to be ordered grows, it appears to be impractical to use
exhaustive search techniques to find the optimal mapping. In this paper we compare
genetic algorithms and simulated annealing, two methods that are widely believed to
be well-suited to non-smooth feature spaces, and find that the genetic algorithm
approach yields superior results. Here we present performance profiles of comparable
implementations of both genetic algorithms and simulated annealing. We have
translated the problem to a form comparable to the shortest-path problem and found
that the ability of a genetic algorithm to combine different partial solutions seems to be
responsible for its superiority over the simulated annealing method. This is because in
the genome mapping problem, as in the Traveling Salesman Problem, good solutions
tend to be rather sparse and because optimal subtours tend to be components of nearly
optimal tours. / Graduation date: 1994
| Identifer | oai:union.ndltd.org:ORGSU/oai:ir.library.oregonstate.edu:1957/36599 |
| Date | 10 August 1993 |
| Creators | Gunnels, John A. |
| Contributors | Cull, Paul |
| Source Sets | Oregon State University |
| Language | en_US |
| Detected Language | English |
| Type | Thesis/Dissertation |
Page generated in 0.0021 seconds