Algorithms in Bioinformatics

We are pleased to present the proceedings of the Third Workshop on Algorithms in Bioinformatics (WABI 2003), which took place on September 15 20, 2003 in Budapest, Hungary. The WABI workshop was part of the four-conference meeting, ALGO 2003, which was locally organized by Dr. Jan os Csirik, Head of the Department of Computer Science, J ozsef Attila University, Budapest. See conferences. hu/ALGO2003/algo_2003. htmfor more details. WABI focuses on discrete algorithms that address important problems in molecular biology, genomics, and genetics, that are founded on sound models, that are computationally e?cient, that have been implemented and tested in simulations and on real datasets, and that provide new biological results. The workshopgoalsareto presentrecentresearchandidentify andexploredirections for future research. We received78 submissionsin responseto the call for papers and 36 were- cepted. We wouldliketo sincerelythank the authorsof allsubmitted papers and the conference participants. We especially thank a terri?c program committee for their diligent and thorough work in reviewing and selecting the papers.

Includes supplementary material: sn.pub/extras

Inhalt
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.