Über die Autorin bzw. den Autor

mourad elloumi, PhD, is Associate Professor in Computer Science, Faculty of Economic Sciences and Management of Tunis (Tunisia), and member of the Unit of Technologies of Information and Communication (UTIC).?He is the author/coauthor of more than forty publications in international journals and conferences. Professor Elloumi was the guest editor of a special issue on biological knowledge discovery and data mining in Knowledge-Based Systems and the coeditor of the proceedings of two international conferences.
 
albert y. zomaya, PhD, is the Chair Professor of High Performance Computing and Networking in the School of Information Technologies at The University of Sydney (Australia). He is the author/coauthor of eight books and more than 400 publications in technical journals and conferences, and the editor of eight books and eight conference volumes. Professor Zomaya is currently an associate editor for twenty journals, the Founding Editor of the Wiley Series on Parallel and Distributed Computing, and a Founding Coeditor of the Wiley Series in Bioinformatics.

Von der hinteren Coverseite

The most comprehensive, practical overview of algorithms in computational molecular biology

Computational molecular biology has emerged from the Human Genome Project as an important discipline for academic research and industrial application. Due to the exponential growth?in the size of biological databases and the increasing intricacy of biological problems, high-performance algorithms are now necessary to deal with errors in biological sequences.?Bringing the most recent research into the forefront of discussion, Algorithms in Computational Molecular Biology is the first in-depth examination of these important algorithms, which are based on the newest and most improved approaches and techniques in the field.

The book's unique coverage offers both a wide range of information―from theintroductory fundamentals right up to the latest, most advanced levels of study―and enough technical depth to be of practical use to working professionals. Organized into seven parts, it addresses:

• Strings processing and application to biological sequences
• Analysis of biological sequences
• Motif finding and structure prediction
• Phylogeny reconstruction
• Microarray data analysis
• Analysis of genomes
• Analysis of biological networks

Also featured are a combination of experiments and simulations that provide not only qualitative but also quantitative insights into this rich field. By covering a wide range of combinatorial problems that arise in computational molecular biology, this book enables researchers, computer scientists, life scientists, mathematicians, graduate students, and senior undergraduates to deal with more complex issues and richer data sets.

Aus dem Klappentext

The most comprehensive, practical overview of algorithms in computational molecular biology
 
Computational molecular biology has emerged from the Human Genome Project as an important discipline for academic research and industrial application. Due to the exponential growth?in the size of biological databases and the increasing intricacy of biological problems, high-performance algorithms are now necessary to deal with errors in biological sequences.?Bringing the most recent research into the forefront of discussion, Algorithms in Computational Molecular Biology is the first in-depth examination of these important algorithms, which are based on the newest and most improved approaches and techniques in the field.
 
The book's unique coverage offers both a wide range of information-from theintroductory fundamentals right up to the latest, most advanced levels of study-and enough technical depth to be of practical use to working professionals. Organized into seven parts, it addresses:
* Strings processing and application to biological sequences
* Analysis of biological sequences
* Motif finding and structure prediction
* Phylogeny reconstruction
* Microarray data analysis
* Analysis of genomes
* Analysis of biological networks
 
Also featured are a combination of experiments and simulations that provide not only qualitative but also quantitative insights into this rich field. By covering a wide range of combinatorial problems that arise in computational molecular biology, this book enables researchers, computer scientists, life scientists, mathematicians, graduate students, and senior undergraduates to deal with more complex issues and richer data sets.

Auszug. © Genehmigter Nachdruck. Alle Rechte vorbehalten.

Algorithms in Computational Molecular Biology

John Wiley & Sons

Chapter One

Christos Makris and Evangelos Theodoridis

1.1 INTRODUCTION

The topic of the chapter is string data structures with applications in the field of computational molecular biology. Let S be a finite alphabet consisting of a set of characters (or symbols). The cardinality of the alphabet denoted by |S| expresses the number of distinct characters in the alphabet. A string or word is an ordered list of zero or more characters drawn from the alphabet. A word or string w of length n is represented by w]1 ... n] = w]1]w]2] ..., w[n], where w[i] [element of] S for 1 = i = n and |w| denotes the length of w. The empty word is the empty sequence (of zero length) and is denoted by e. A list of characters of w, appearing in consecutive positions, is called a substring of w, denoted by w [i ... j], where i and j are the starting and ending positions, respectively. If the substring starts at position 1, then it is called a prefix, whereas if it ends at position n, then it is called a suffix of w. However, an ordered list of characters of w that are not necessarily consecutive is called a subsequence of w.

Strings and subsequences appear in a plethora of computational molecular biology problems because the basic types of DNA, RNA, and protein molecules can be represented as strings—pieces of DNA as strings over the alphabet {A, C, G, T} (representing the four bases adenine, cytosine, guanine, and thymine, respectively), pieces of RNA as strings over the alphabet {A, C, G, U} (with uracil replacing thymine), and proteins as strings over an alphabet of 20, corresponding to the 20 amino acid residues.

The basic string algorithmic problems that develop in computational molecular biology are:

? Exact pattern matching: given a pattern P and a text T to locate the occurrences of P into T ? Approximate pattern matching: given a pattern P, a text T, a similarity metric distance function d(), and a threshold parameter k to locate all positions i and j such that d(P, T_{i ... j}) = k ? Sequence alignment: given two string sequences, T₁ and T₂, try to find the best alignment between the two sequences according to various criteria. The alignment can be either local or global. A special case of this problem, which has great biological significance, is the longest common subsequence problem in which we try to locate the longest subsequence that is common to both sequences ? Multiple approximate and exact pattern matching in which more than two strings are involved into the computation ? String clustering: given a set of stings, cluster them into a set of clusters according to the distance between the involved strings; this problem has great biological significance because DNA sequence clustering and assembling overlapping DNA sequences are critical operations when extracting useful biological knowledge ? Efficient implementation of indexing techniques for storing and retrieving information from biological databases

Besides these classical string algorithmic problems, there are also applications that demand the processing of strings whose form deviates from the classical definition. The most known category of such variations are the weighted strings that are used to model molecular weighted sequences. A molecular weighted sequence is a molecular sequence (a sequence of either nucleotides or amino acids) in which in every position can be stored a set of characters each having a certain weight assigned. This weight can model either the probability of appearance or the stability of the character's contribution to the molecular complex. These sequences appear in applications concerning the DNA assembly process or in the modeling of the binding sites of regulatory proteins. In the first case, the DNA must be divided into many short strings that are sequenced separately and then are used to assemble the sequence of the full string; this reassembling introduces a degree of uncertainty that initially was expressed with the use of the "don't care" character denoted as "*," which has the property of matching against any symbol in the given alphabet. It is possible, though, that scientists are able to be more exact in their modeling and determine the probability of a certain character to appear at a position; j then a position that previously was characterized as a wild card is replaced by a probability of appearance for each of the characters of the alphabet and such a sequence is modeled as a weighted sequence. In the second case, when a molecular weighted sequence models the binding site of a regulatory protein, each base in a candidate motif instance makes some positive, negative, or neutral contribution to the binding stability of the DNA-protein complex, and the weights assigned to each character can be thought of as modeling those effects. If the sum of the individual contributions is greater than a threshold, then the DNA–protein complex can be considered stable enough to be functional.

A related notion is the notion of an indeterminate or (equivalently in the scientific literature) a degenerate string. This specific term refers to strings in which each position contains a set of characters instead of a simple character; in these strings, the match operation is replaced by the subset operation. The need for processing efficiently such strings is driven by applications in computational biology cryptanalysis and musicology. In computational biology, DNA sequences still may be considered to match each other if letter A (respectively, C) is juxtaposed with letter T (respectively, G); moreover, indeterminate strings can model effectively polymorphism in protein coding regions. In cryptanalysis, undecoded symbols can be modeled as the set or characters that are candidates for the specific position, whereas in music, single notes may match chords or a set of notes.

Perhaps the most representative application of indeterminate strings is haplotype inference. A haplotype is a DNA sequence that has been inherited by one parent. A description of the data from a single copy is called a haplotype, whereas a description of the mixed data on the two copies is called a genotype. The underlying data that form a haplotype is either the full DNA sequence in the region or, more commonly, is the values of only DNA positions that are single nucleotide polymorphisms (SNPs). Given an input set D of n genotype vectors, a solution to the haplotype inference problem is a set of n pairs of binary strings one pair for each genotype; for any genotype g, the associated binary vectors v₁, v₂ must be a "feasible resolution" of g into two haplotypes that could explain how g was created. Several algorithms have been proposed for the haplotype...