Title

Genetic Algorithms, Operators, And Dna Fragment Assembly

Keywords

building blocks; DNA fragment assembly; edge-recombination crossover; genetic algorithms; human genome project; ordering problems

Abstract

We study different genetic algorithm operators for one permutation problem associated with the Human Genome Project—the assembly of DNA sequence fragments from a parent clone whose sequence is unknown into a consensus sequence corresponding to the parent sequence. The sorted-order representation, which does not require specialized operators, is compared with a more traditional permutation representation, which does require specialized operators. The two representations and their associated operators are compared on problems ranging from 2K to 34K base pairs (KB). Edge-recombination crossover used in conjunction with several 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 are exploited at progressively higher levels through “macro-operators.” This significantly improves performance. © 1995, Kluwer Academic Publishers. All rights reserved.

Publication Date

1-1-1995

Publication Title

Machine Learning

Volume

21

Issue

1

Number of Pages

11-33

Document Type

Article

Personal Identifier

scopus

DOI Link

https://doi.org/10.1023/A:1022613513712

Socpus ID

0029387798 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/0029387798

This document is currently not available here.

Share

COinS