Bioinformatics Algorithms

Presents algorithmic techniques for solving problems in bioinformatics, including applications that shed new light on molecular biology This book introduces algorithmic techniques in bioinformatics, emphasizing their application to solving novel problems in post-genomic molecular biology. Beginning with a thought-provoking discussion on the role of algorithms in twenty-first-century bioinformatics education, Bioinformatics Algorithms covers: General algorithmic techniques, including dynamic programming, graph-theoretical methods, hidden Markov models, the fast Fourier transform, seeding, and approximation algorithms Algorithms and tools for genome and sequence analysis, including formal and approximate models for gene clusters, advanced algorithms for non-overlapping local alignments and genome tilings, multiplex PCR primer set selection, and sequence/network motif finding Microarray design and analysis, including algorithms for microarray physical design, missing value imputation, and meta-analysis of gene expression data Algorithmic issues arising in the analysis of genetic variation across human population, including computational inference of haplotypes from genotype data and disease association search in case/control epidemiologic studies Algorithmic approaches in structural and systems biology, including topological and structural classification in biochemistry, and prediction of protein-protein and domain-domain interactions Each chapter begins with a self-contained introduction to a computational problem; continues with a brief review of the existing literature on the subject and an in-depth description of recent algorithmic and methodological developments; and concludes with a brief experimental study and a discussion of open research challenges. This clear and approachable presentation makes the book appropriate for researchers, practitioners, and graduate students alike.

Presents algorithmic techniques for solving problems inbioinformatics, including applications that shed new light onmolecular biologyThis book introduces algorithmic techniques in bioinformaticsemphasizing their application to solving novel problems inpost-genomic molecular biology. Beginning with a thought-provokingdiscussion on the role of algorithms in twenty-first-centurybioinformatics education, Bioinformatics Algorithms covers:* General algorithmic techniques, including dynamic programminggraph-theoretical methods, hidden Markov models, the fast Fouriertransform, seeding, and approximation algorithms* Algorithms and tools for genome and sequence analysis, includingformal and approximate models for gene clusters, advancedalgorithms for non-overlapping local alignments and genome tilingsmultiplex PCR primer set selection, and sequence/network motiffinding* Microarray design and analysis, including algorithms formicroarray physical design, missing value imputation, andmeta-analysis of gene expression data* Algorithmic issues arising in the analysis of genetic variationacross human population, including computational inference ofhaplotypes from genotype data and disease association search incase/control epidemiologic studies* Algorithmic approaches in structural and systems biologyincluding topological and structural classification inbiochemistry, and prediction of protein-protein and domain-domaininteractionsEach chapter begins with a self-contained introduction to acomputational problem; continues with a brief review of theexisting literature on the subject and an in-depth description ofrecent algorithmic and methodological developments; and concludeswith a brief experimental study and a discussion of open researchchallenges. This clear and approachable presentation makes the bookappropriate for researchers, practitioners, and graduate studentsalike.

Preface ixContributors xi1 Educating Biologists in the 21st Century: Bioinformatics Scientists versus Bioinformatics Technicians 1Pavel PevznerPart I Techniques 72 Dynamic Programming Algorithms for Biological Sequence and Structure Comparison 9Yuzhen Ye and Haixu Tang3 Graph Theoretical Approaches to Delineate Dynamics of Biological Processes 29Teresa M. Przytycka and Elena Zotenko4 Advances in Hidden Markov Models for Sequence Annotation 55Brona Brejová, Daniel G. Brown, and Tomás Vinar5 Sorting- and FFT-Based Techniques in the Discovery of Biopatterns 93Sudha Balla, Sanguthevar Rajasekaran, and Jaime Davila6 A Survey of Seeding for Sequence Alignment 117Daniel G. Brown7 The Comparison of Phylogenetic Networks: Algorithms and Complexity 143Paola Bonizzoni, Gianluca Della Vedova, Riccardo Dondi, and Giancarlo MauriPart II Genome and Sequence Analysis 1758 Formal Models of Gene Clusters 177Anne Bergeron, Cedric Chauve, and Yannick Gingras9 Integer Linear Programming Techniques for Discovering Approximate Gene Clusters 203Sven Rahmann and Gunnar W. Klau10 Efficient Combinatorial Algorithms for DNA Sequence Processing 223Bhaskar DasGupta and Ming-Yang Kao11 Algorithms for Multiplex PCR Primer Set Selection with Amplification Length Constraints 241K.M. Konwar, I.I. Mandoiu, A.C. Russell, and A.A. Shvartsman12 Recent Developments in Alignment and Motif Finding for Sequences and Networks 259Sing-Hoi SzePart III Microarray Design and Data Analysis 27713 Algorithms for Oligonucleotide Microarray Layout 279Sérgio A. De Carvalho Jr. and Sven Rahmann14 Classification Accuracy Based Microarray Missing Value Imputation 303Yi Shi, Zhipeng Cai, and Guohui Lin15 Meta-Analysis of Microarray Data 329Saumyadipta Pyne, Steve Skiena, and Bruce FutcherPart IV Genetic Variation Analysis 35316 Phasing Genotypes Using a Hidden Markov Model 355P. Rastas, M. Koivisto, H. Mannila, and E. Ukkonen17 Analytical and Algorithmic Methods for Haplotype Frequency Inference: What Do They Tell Us? 373Steven Hecht Orzack, Daniel Gusfield, Lakshman Subrahmanyan, Laurent Essioux, and Sebastien Lissarrague18 Optimization Methods for Genotype Data Analysis in Epidemiological Studies 395Dumitru Brinza, Jingwu He, and Alexander ZelikovskyPart V Structural and Systems Biology 41719 Topological Indices in Combinatorial Chemistry 419Sergey Bereg20 Efficient Algorithms for Structural Recall in Databases 439Hao Wang, Patra Volarath, and Robert W. Harrison21 Computational Approaches to Predict Protein-Protein and Domain-Domain Interactions 465Raja Jothi and Teresa M. PrzytyckaIndex 493