This book constitutes the refereed proceedings of the 8th International Workshop on Algorithms in Bioinformatics, WABI 2008, held in Karlsruhe, Germany, in September 2008 as part of the ALGO 2008 meeting. The 32 revised full papers presented together with the abstract of a keynote talk were carefully reviewed and selected from 81 submissions. All current issues of algorithms in bioinformatics are addressed, reaching from mathematical tools to experimental studies of approximation algorithms and reports on significant computational analyses. The topics range in biological applicability from genome mapping, to sequence assembly, to microarray quality, to phylogenetic inference, to molecular modeling.
Multichromosomal Genome Median and Halving Problems.- A Branch-and-Bound Method for the Multichromosomal Reversal Median Problem.- Decompositions of Multiple Breakpoint Graphs and Rapid Exact Solutions to the Median Problem.- Read Mapping Algorithms for Single Molecule Sequencing Data.- Exact Transcriptome Reconstruction from Short Sequence Reads.- Post-Hybridization Quality Measures for Oligos in Genome-Wide Microarray Experiments.- NAPX: A Polynomial Time Approximation Scheme for the Noah's Ark Problem.- Minimum Common String Partition Parameterized.- Hardness and Approximability of the Inverse Scope Problem.- Rapid Neighbour-Joining.- Efficiently Computing Arbitrarily-Sized Robinson-Foulds Distance Matrices.- Efficient Genome Wide Tagging by Reduction to SAT.- Computing the Minimal Tiling Path from a Physical Map by Integer Linear Programming.- An Efficient Lagrangian Relaxation for the Contact Map Overlap Problem.- A Faster Algorithm for RNA Co-folding.- An Automated Combination of Kernels for Predicting Protein Subcellular Localization.- Fast Target Set Reduction for Large-Scale Protein Function Prediction: A Multi-class Multi-label Machine Learning Approach.- Multiple Instance Learning Allows MHC Class II Epitope Predictions Across Alleles.- An Algorithm for Orienting Graphs Based on Cause-Effect Pairs and Its Applications to Orienting Protein Networks.- Enumerating Precursor Sets of Target Metabolites in a Metabolic Network.- Boosting the Performance of Inference Algorithms for Transcriptional Regulatory Networks Using a Phylogenetic Approach.- Fast Bayesian Haplotype Inference Via Context Tree Weighting.- Genotype Sequence Segmentation: Handling Constraints and Noise.- Constructing Phylogenetic Supernetworks from Quartets.- Summarizing Multiple Gene Trees Using Cluster Networks.- Fast and Adaptive Variable Order Markov Chain Construction.- Computing Alignment Seed Sensitivity with Probabilistic Arithmetic Automata.- The Relation between Indel Length and Functional Divergence: A Formal Study.- Detecting Repeat Families in Incompletely Sequenced Genomes.- Novel Phylogenetic Network Inference by Combining Maximum Likelihood and Hidden Markov Models.- A Local Move Set for Protein Folding in Triangular Lattice Models.- Protein Decoy Generation Using Branch and Bound with Efficient Bounding.