A comparison of simulated annealing and genetic algorithms for the genome mapping problems Public Deposited

http://ir.library.oregonstate.edu/concern/graduate_thesis_or_dissertations/g445cj68q

Descriptions

Attribute NameValues
Creator
Abstract or Summary
  • 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.
Resource Type
Date Available
Date Copyright
Date Issued
Degree Level
Degree Name
Degree Field
Degree Grantor
Commencement Year
Advisor
Academic Affiliation
Non-Academic Affiliation
Subject
Rights Statement
Peer Reviewed
Language
Digitization Specifications
  • File scanned at 300 ppi (Monochrome, 8-bit Grayscale) using ScandAll PRO 1.8.1 on a Fi-6670 in PDF format. CVista PdfCompressor 4.0 was used for pdf compression and textual OCR.
Replaces
Additional Information
  • description.provenance : Approved for entry into archive by Patricia Black(patricia.black@oregonstate.edu) on 2013-02-06T20:13:51Z (GMT) No. of bitstreams: 1 GunnelsJohnA1994.pdf: 7362686 bytes, checksum: 2fe4920201cf1ee1a25882ea5a21b307 (MD5)
  • description.provenance : Approved for entry into archive by Patricia Black(patricia.black@oregonstate.edu) on 2013-01-09T17:30:44Z (GMT) No. of bitstreams: 1 GunnelsJohnA1994.pdf: 7362686 bytes, checksum: 2fe4920201cf1ee1a25882ea5a21b307 (MD5)
  • description.provenance : Made available in DSpace on 2013-02-06T20:13:51Z (GMT). No. of bitstreams: 1 GunnelsJohnA1994.pdf: 7362686 bytes, checksum: 2fe4920201cf1ee1a25882ea5a21b307 (MD5) Previous issue date: 1993-08-10
  • Figures in original are black and white copies. Best scan available.
  • description.provenance : Submitted by Sergio Trujillo (jstscanner@gmail.com) on 2012-12-13T23:42:00Z No. of bitstreams: 1 GunnelsJohnA1994.pdf: 7362686 bytes, checksum: 2fe4920201cf1ee1a25882ea5a21b307 (MD5)

Relationships

Parents:

This work has no parents.

Last modified

Downloadable Content

Download PDF

Items