GENETIC ALGORITHMS, OPERATORS, AND DNA FRAGMENT ASSEMBLY

We study different genetic algorithm operators for one permutation pro blem associated with the Human Genome Project-the assembly of DNA sequ ence fragments from a parent clone whose sequence is unknown into a co nsensus sequence corresponding to the parent sequence. The sorted-orde r representation, which does not require specialized operators, is com pared with a more traditional permutation representation, which does r equire specialized operators. The two representations and their associ ated operators are compared on problems ranging from 2K to 34K base pa irs (KB). Edge-recombination crossover used in conjunction with severa l specialized operators is found to perform best in these experiments; these operators solved a 10KB sequence, consisting of 177 fragments, with no manual intervention. Natural building blocks in the problem ar e exploited at progressively higher levels through ''macro-operators.' ' This significantly improves performance.