This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Blazewicz, J. Articles by Weglarz, J. Search for Related Content

DNA Sequencing by Hybridization via Genetic Search

Institute of Computing Science, Pozna University of Technology, Piotrowo 2, 60-965 Pozna, Poland, and the Institute of Bioorganic Chemistry, Polish Academy of Sciences, Noskowskiego 12/14, 61-704 Pozna, Poland
Department of Industrial Engineering, Koç University, Istanbul, Turkey
Institute of Computing Science, Pozna University of Technology, Piotrowo 2, 60-965 Pozna, Poland, and the Institute of Bioorganic Chemistry, Polish Academy of Sciences, Noskowskiego 12/14, 61-704 Pozna, Poland
Institute of Computing Science, Pozna University of Technology, Piotrowo 2, 60-965 Pozna, Poland, and the Institute of Bioorganic Chemistry, Polish Academy of Sciences, Noskowskiego 12/14, 61-704 Pozna, Poland
jblazewicz{at}cs.put.poznan.pl
coguz{at}ku.edu.tr
aswiercz{at}cs.put.poznan.pl
jweglarz{at}cs.put.poznan.pl

An innovative approach to DNA sequencing by hybridization utilizes isothermic oligonucleotide libraries. In this paper, we demonstrate the utility of a genetic algorithm for the combinatorial portion of this new approach by incorporating characteristics of DNA sequencing by hybridization in addition to isothermic oligonucleotide libraries. Specialized crossover and mutation operators were developed for this purpose. After initial experiments for parameter adjustment, the performance of the genetic algorithm approach was evaluated with respect to previous methods in the literature. The results indicate that the proposed new approach is superior to previous approaches. The proposed new crossover operator that inherits some features of the structured weighted combinations might also be of value for some other combinatorial problems, including the traveling salesman problem.

Subject classifications: analysis of algorithms: metaheuristics; health care: bioinformatics; health care: DNA sequencing; programming: integer; algorithms: heuristic.
History: Received May 2004; revision received September 2005; accepted October 2005.