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.
Author(s): Mohamed Ibrahim Abouelhoda, Enno Ohlebusch (auth.), Gary Benson, Roderic D. M. Page (eds.)
Series: Lecture Notes in Computer Science 2812 : Lecture Notes in Bioinformatics
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 2003
Language: English
Pages: 534
Tags: Algorithm Analysis and Problem Complexity; Data Structures; Computation by Abstract Devices; Mathematics of Computing; Database Management; Bioinformatics
Front Matter....Pages -
A Local Chaining Algorithm and Its Applications in Comparative Genomics....Pages 1-16
Common Intervals of Two Sequences....Pages 17-24
A Systematic Statistical Analysis of Ion Trap Tandem Mass Spectra in View of Peptide Scoring....Pages 25-38
Vector Seeds: An Extension to Spaced Seeds Allows Substantial Improvements in Sensitivity and Specificity....Pages 39-54
A Stochastic Approach to Count RNA Molecules Using DNA Sequencing Methods....Pages 55-62
A Method to Detect Gene Structure and Alternative Splice Sites by Agreeing ESTs to a Genomic Sequence....Pages 63-77
Optimal DNA Signal Recognition Models with a Fixed Amount of Intrasignal Dependency....Pages 78-94
New Algorithm for the Simplified Partial Digest Problem....Pages 95-110
Noisy Data Make the Partial Digest Problem NP -hard....Pages 111-123
Pattern Discovery Allowing Wild-Cards, Substitution Matrices, and Multiple Score Functions....Pages 124-138
A Combinatorial Approach to Automatic Discovery of Cluster-Patterns....Pages 139-150
Dynamic Programming Algorithms for Two Statistical Problems in Computational Biology....Pages 151-164
Consensus Networks: A Method for Visualising Incompatibilities in Collections of Trees....Pages 165-176
Efficient Generation of Uniform Samples from Phylogenetic Trees....Pages 177-189
New Efficient Algorithm for Detection of Horizontal Gene Transfer Events....Pages 190-201
Ancestral Maximum Likelihood of Evolutionary Trees Is Hard....Pages 202-215
A Linear-Time Majority Tree Algorithm....Pages 216-227
Bayesian Phylogenetic Inference under a Statistical Insertion-Deletion Model....Pages 228-244
Better Hill-Climbing Searches for Parsimony....Pages 245-258
Computing Refined Buneman Trees in Cubic Time....Pages 259-270
Distance Corrections on Recombinant Sequences....Pages 271-286
Parsimonious Reconstruction of Sequence Evolution and Haplotype Blocks....Pages 287-302
Identifying Blocks and Sub-populations in Noisy SNP Data....Pages 303-319
Designing Optimally Multiplexed SNP Genotyping Assays....Pages 320-338
Minimum Recombinant Haplotype Configuration on Tree Pedigrees....Pages 339-353
Efficient Energy Computation for Monte Carlo Simulation of Proteins....Pages 354-373
Speedup LP Approach to Protein Threading via Graph Reduction....Pages 374-388
Homology Modeling of Proteins Using Multiple Models and Consensus Sequence Alignment....Pages 389-401
Side-Chain Structure Prediction Based on Dead-End Elimination: Single Split DEE-criterion Implementation and Elimination Power....Pages 402-416
A Large Version of the Small Parsimony Problem....Pages 417-432
Optimal Multiple Parsimony Alignment with Affine Gap Cost Using a Phylogenetic Tree....Pages 433-446
Composition Alignment....Pages 447-461
Match Chaining Algorithms for cDNA Mapping....Pages 462-475
Sequencing from Compomers: Using Mass Spectrometry for DNA De-Novo Sequencing of 200+ nt....Pages 476-497
Bounds for Resequencing by Hybridization....Pages 498-511
Selecting Degenerate Multiplex PCR Primers....Pages 512-526
Back Matter....Pages -
