Metaheuristics for String Problems in Bio-informatics

7Conclusions

Here, we will provide references and short descriptions of optimization problems from the bio-informatics field that not have been dealt with in detail so far. In particular, these include DNA sequencing problems and founder sequence reconstruction.

7.1. DNA sequencing

DNA sequencing is the process of determining the precise order of the nucleotides in a DNA molecule. The knowledge of the precise composition of DNA sequences has become very important in numerous application fields such as medical diagnosis, biotechnology, forensic biology, virology and biological systematics. Computational methods such as metaheuristics have played an important role in DNA sequencing technology. The first basic DNA sequencing technologies were developed in the 1970s (see [JAY 74]). An example of a basic DNA sequencing technology is shotgun sequencing [STA 79]. Small genomes (4,000 to 7,000 base pairs) had already been sequenced by means of shotgun sequencing in 1997 [STA 79]. The first of the next-generation sequencing technologies, known as massively parallel signature sequencing, was developed in the 1990s [BRE 00]. Another example is DNA sequencing by hybridization [BAI 88, LYS 87, DRM 89]. In the following section, we will provide several examples in which metaheuristics play an important role.

7.1.1. DNA fragment assembly

The so-called DNA fragment assembly problem is a computational problem that is a major component of DNA sequencing, often on the basis of shotgun sequencing. ...