Metaheuristics for String Problems in Bio-informatics

Christian Blum, Paola Festa

• Publisher: Wiley-ISTE
• Year: 2016
• Print ISBN: 9781848218123
• eBook ISBN: 9781119136811
• Edition: 1
• Topic: Computer Science
• Subtopic: Computer Engineering
• Index: Computer Science

So-called string problems are abundant in bioinformatics and computational biology. New optimization problems dealing with DNA or protein sequences are constantly arising and researchers are highly in need of efficient optimization techniques for solving them.

One obstacle for optimization practitioners is the atypical nature of these problems which require an interdisciplinary approach in order to solve them efficiently and accurately.

1
Introduction

In computer science, a string s is defined as a finite sequence of characters from a finite alphabet Σ. Apart from the alphabet, an important characteristic of a string s is its length which, in this book, will be denoted by |s|. A string is, generally, understood to be a data type i.e. a string is used to represent and store information. For example, words in a specific language are stored in a computer as strings. Even the entire text may be stored by means of strings. Apart from fields such as information and text processing, strings arise in the field of bioinformatics. This is because most of the genetic instructions involved in the growth, development, functioning and reproduction of living organisms are stored in a molecule which is known as deoxyribonucleic acid (DNA) which can be represented in the form of a string in the following way. DNA is a nucleic acid that consists of two biopolymer strands forming a double helix (see Figure 1.1). The two strands of DNA are called polynucleotides as they are composed of simpler elements called nucleotides. Each nucleotide consists of a nitrogen-containing nucleobase as well as deoxyribose and a phosphate group. The four different nucleobases of DNA are cytosine (C), guanine (G), adenine (A) and thymine (T). Each DNA strand is a sequence of nucleotides that are joined to one another by covalent bonds between the sugar of one nucleotide and the phosphate of the next. This results in an alternating sugar–phosphate backbone (see Figure 1.1). Furthermore, hydrogen bonds bind the bases of the two separate polynucleotide strands to make double-stranded DNA. As a result, A can only bind with T and C can only bind with G. Therefore, a DNA molecule can be stored as a string of symbols from Σ = {A, C, T, G} that represent one of the two polynucleotide strands. Similarly, most proteins can be stored as a string of letters from an alphabet of 20 letters, representing the 20 standard amino acids that constitute most proteins.

Figure 1.1. DNA double helix (image courtesy of Wikipedia)

As a result, many optimization problems in the field of computational biology are concerned with strings representing, for example, DNA or protein sequences. In this book we will focus particularly on recent works concerning string problems that can be expressed in terms of combinatorial optimization (CO). In early work by Papadimitriou and Steiglitz [PAP 82], a CO problem

is defined by a tuple (

, f), where

is a finite set of objects and

is a function that assigns a non-negative cost value to each of the objects s ∈

. Solving a CO problem

requires us to find an object s^∗ of minimum cost value¹. As a classic academic example, consider the well-known traveling salesman problem (TSP). In the case of the TSP, set

consists of all Hamiltonian cycles in a completely connected, undirected graph with positive edge weights. The objective function value of such a Hamiltonian cycle is the sum of the weights of its edges.

Unfortunately, most CO problems are difficult to optimality solve in practice. ...

Table of contents

• Cover
• Table of Contents
• Dedication
• Title
• Copyright
• Preface
• Acknowledgments
• List of Acronyms
• 1 Introduction
• 2 Minimum Common String Partition Problem
• 3 Longest Common Subsequence Problems
• 4 The Most Strings With Few Bad Columns Problem
• 5 Consensus String Problems
• 6 Alignment Problems
• 7 Conclusions
• Bibliography
• Index
• End User License Agreement