Algorithms in Bioinformatics

This book constitutes the refereed proceedings of the Third International Workshop on Algorithms in Bioinformatics, WABI 2003, held in Budapest, Hungary, in September 2003. The 36 revised full papers presented were carefully reviewed and selected from 78 submissions. The papers are organized in topical sections on comparative genomics, database searching, gene finding and expression, genome mapping, pattern and motif discovery, phylogenetic analysis, polymorphism, protein structure, sequence alignment, and string algorithms.

Contenu

Comparative Genomics.- A Local Chaining Algorithm and Its Applications in Comparative Genomics.- Common Intervals of Two Sequences.- A Systematic Statistical Analysis of Ion Trap Tandem Mass Spectra in View of Peptide Scoring.- Vector Seeds: An Extension to Spaced Seeds Allows Substantial Improvements in Sensitivity and Specificity.- Gene Finding and Expression.- A Stochastic Approach to Count RNA Molecules Using DNA Sequencing Methods.- A Method to Detect Gene Structure and Alternative Splice Sites by Agreeing ESTs to a Genomic Sequence.- Optimal DNA Signal Recognition Models with a Fixed Amount of Intrasignal Dependency.- Genome Mapping.- New Algorithm for the Simplified Partial Digest Problem.- Noisy Data Make the Partial Digest Problem NP-hard.- Pattern and Motif Discovery.- Pattern Discovery Allowing Wild-Cards, Substitution Matrices, and Multiple Score Functions.- A Combinatorial Approach to Automatic Discovery of Cluster-Patterns.- Dynamic Programming Algorithms for Two Statistical Problems in Computational Biology.- Phylogenetic Analysis.- Consensus Networks: A Method for Visualising Incompatibilities in Collections of Trees.- Efficient Generation of Uniform Samples from Phylogenetic Trees.- New Efficient Algorithm for Detection of Horizontal Gene Transfer Events.- Ancestral Maximum Likelihood of Evolutionary Trees Is Hard.- A Linear-Time Majority Tree Algorithm.- Bayesian Phylogenetic Inference under a Statistical Insertion-Deletion Model.- Better Hill-Climbing Searches for Parsimony.- Computing Refined Buneman Trees in Cubic Time.- Distance Corrections on Recombinant Sequences.- Parsimonious Reconstruction of Sequence Evolution and Haplotype Blocks.- Polymorphism.- Identifying Blocks and Sub-populations in Noisy SNP Data.- Designing Optimally Multiplexed SNP Genotyping Assays.- Minimum Recombinant Haplotype Configuration on Tree Pedigrees.- Protein Structure.- Efficient Energy Computation for Monte Carlo Simulation of Proteins.- Speedup LP Approach to Protein Threading via Graph Reduction.- Homology Modeling of Proteins Using Multiple Models and Consensus Sequence Alignment.- Side-Chain Structure Prediction Based on Dead-End Elimination: Single Split DEE-criterion Implementation and Elimination Power.- Sequence Alignment.- A Large Version of the Small Parsimony Problem.- Optimal Multiple Parsimony Alignment with Affine Gap Cost Using a Phylogenetic Tree.- Composition Alignment.- String Algorithms.- Match Chaining Algorithms for cDNA Mapping.- Sequencing from Compomers: Using Mass Spectrometry for DNA De-Novo Sequencing of 200+ nt.- Bounds for Resequencing by Hybridization.- Selecting Degenerate Multiplex PCR Primers.