title: Coevolving solutions to the shortest common superstring problem.
abstract: The shortest common superstring (SCS) problem, known to be NP-Complete, seeks the shortest string that contains all strings from a given set. In this paper we compare four approaches for finding solutions to the SCS problem: a standard genetic algorithm, a novel cooperative-coevolutionary algorithm, a benchmark greedy algorithm, and a parallel coevolutionary-greedy approach. We show the coevolutionary approach produces the best results, and discuss directions for future research.
authors.affiliation: Department of Computer Science, Ben-Gurion University, P.O. Box 653, Beer-Sheva 84105, Israel. assafza@cs.bgu.ac.il
authors.forename: Assaf
authors.initials: A
authors.lastname: Zaritsky
authors.forename: Moshe
authors.initials: M
authors.lastname: Sipper
mesh_terms: D000465:Algorithms; D000818:Animals; D005075:Biological Evolution; D003198:Computer Simulation; D017124:Conserved Sequence; D006801:Humans; D008957:Models, Genetic; D009716:Numerical Analysis, Computer-Assisted; D016415:Sequence Alignment / Q000379:methods*; D017421:Sequence Analysis / Q000379:methods*; D017385:Sequence Homology