Optimization Approaches for Solving String Selection Problems

verfasst von: Elisa Pappalardo, Panos M. Pardalos, Giovanni Stracquadanio

Verlag: Springer New York

Buchreihe : SpringerBriefs in Optimization

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

Optimization Approaches for Solving String Selection Problems provides an overview of optimization methods for a wide class of genomics-related problems in relation to the string selection problems. This class of problems addresses the recognition of similar characteristics or differences within biological sequences. Specifically, this book considers a large class of problems, ranging from the closest string and substring problems, to the farthest string and substring problems, to the far from most string problem. Each problem includes a detailed description, highlighting both biological and mathematical features and presents state-of-the-art approaches.

This Brief provides a quick introduction of optimization methods for string selection problems for young scientists and a detailed description of the mathematical and computational methods developed for experts in the field of optimization who want to deepen their understanding of the string selection problems. Researchers, practitioners and graduate students in the field of Computer Science, Operation Research, Mathematics, Computational Biology and Biomedicine will find this book useful.

Inhaltsverzeichnis

Frontmatter

Chapter 1. Biological Sequences

Abstract

Starting with the introduction of the first chain-termination method for DNA sequencing in 1977 by Sanger et al., the ability of unveiling the genome of an organism marked a breakthrough moment in biology. Nowadays, the deluge of data provided by high-throughput sequencing technologies continuously requires the design of fast and efficient analysis methods. Moreover, the progress of DNA synthesis technologies requires algorithms to design molecules with specific functions. In this chapter, we introduce some basic biological concepts and how DNA sequences are obtained from an organism through sequencing, to set the fundamentals to understand the importance of string selection algorithms.

Elisa Pappalardo, Panos M. Pardalos, Giovanni Stracquadanio

Chapter 2. Strings: Theory, Properties and Applications

Abstract

Genomic and proteomic data can be represented as sequences over the nucleotides and amino acids alphabets, and many tasks require algorithms working on strings. This chapter introduces the formalism to deal with sequences and the definition of distance metrics, largely used in string selection methods.

Elisa Pappalardo, Panos M. Pardalos, Giovanni Stracquadanio

Chapter 3. Mathematical Optimization

Abstract

Mathematical Optimization is an interdisciplinary branch of applied mathematics, related to the fields of Operations Research, Computational Complexity, and Algorithm Theory. It can be informally defined as the science of finding the “best” solution from a set of available alternatives, where the notion of “best” is intrinsically related to the specific problem addressed. Nowadays, optimization problems arise in all sorts of areas and are countless in everyday life, such as in engineering, microelectronics, telecommunications, biomedicine, genetics, proteomics, economics, finance, and physics. However, in spite of the proliferation of optimization algorithms, there is no universal method suitable for all optimization problems, and the choice of the “most appropriate method” to solve the specific problem is demanded to the user. With this in mind, in this chapter we address some general questions about optimization problems and their solutions, in order to provide a background knowledge of the issues analyzed later.

Elisa Pappalardo, Panos M. Pardalos, Giovanni Stracquadanio

Chapter 4. String Selection Problems

Abstract

The increasing amount of genomic data and the ability to synthesize artificial DNA constructs poses a series of challenging problems involving the identification and design of sequences with specific properties. We address the identification of such sequences; many of these problems present challenges both at biological and computational level. In this chapter, we introduce the main string selection problems and the theoretical and experimental results for the most important instances.

Elisa Pappalardo, Panos M. Pardalos, Giovanni Stracquadanio

Titel: Optimization Approaches for Solving String Selection Problems
verfasst von: Elisa Pappalardo
Panos M. Pardalos
Giovanni Stracquadanio
Verlag: Springer New York
Electronic ISBN: 978-1-4614-9053-1
Print ISBN: 978-1-4614-9052-4
DOI: https://doi.org/10.1007/978-1-4614-9053-1