.
Consider the genetic mapping example introduced in Example 3.1. shows some data for 100 simulated data sequences for a chromosome of length 12. The left panel of this figure shows the data under the true genetic map ordering, and the right panel shows the actual data, with the ordering unknown to the analyst. The data are available from the website for this book.
a.
Apply a random starts local search approach to estimate the genetic map (i.e., the ordering and the genetic distances). Let neighborhoods consist of 20 orderings that differ from the current ordering by randomly swapping the placement of two alleles. Move to the best candidate in the neighborhood, thereby taking a random descent step. Begin with a small number of starts of limited length, to gauge the computational difficulty of the problem; then report the best results you obtained within reasonable limits on the computational burden. Comment on your results, the performance of the algorithm, and ideas for improved search. [Hint: Note that the orderings (θj1, θj2, . . . , θj12 ) and (θj12, θj11, . . . , θj1 ) represent identical chromosomes read from either end.]
b.
Apply an algorithm for random starts local search via steepest descent to estimate the genetic map. Comment on your results and the performance of the algorithm. This problem is computationally demanding and may require a fast computer.
3.6.
Consider the genetic mapping data described in Problem 3.5.
a.
Apply a genetic algorithm to estimate the genetic map (i.e., the ordering and the genetic distances). Use the order crossover method. Begin with a small run to gauge the computational difficulty of the problem, then report your results for a run using reasonable limits on the computational burden. Comment on your results, the performance of the algorithm, and ideas for improved search.
b.
Compare the speed of fitness improvements achieved with the order crossover and the edge-recombination crossover strategies.
c.
Attempt any other heuristic search method for these data. Describe your implementation, its speed, and the results.