Algorithms in Bioinformatics: 8th International Workshop, WABI 2008, Karlsruhe, Germany, September 15-19, 2008. Proceedings

Eric Tannier, Chunfang Zheng, David Sankoff (auth.), Keith A. Crandall, Jens Lagergren (eds.)3540873600, 9783540873600

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.

Table of contents :
Front Matter….Pages –
Multichromosomal Genome Median and Halving Problems….Pages 1-13
A Branch-and-Bound Method for the Multichromosomal Reversal Median Problem….Pages 14-24
Decompositions of Multiple Breakpoint Graphs and Rapid Exact Solutions to the Median Problem….Pages 25-37
Read Mapping Algorithms for Single Molecule Sequencing Data….Pages 38-49
Exact Transcriptome Reconstruction from Short Sequence Reads….Pages 50-63
Post-Hybridization Quality Measures for Oligos in Genome-Wide Microarray Experiments….Pages 64-75
NAPX: A Polynomial Time Approximation Scheme for the Noah’s Ark Problem….Pages 76-86
Minimum Common String Partition Parameterized….Pages 87-98
Hardness and Approximability of the Inverse Scope Problem….Pages 99-112
Rapid Neighbour-Joining….Pages 113-122
Efficiently Computing Arbitrarily-Sized Robinson-Foulds Distance Matrices….Pages 123-134
Efficient Genome Wide Tagging by Reduction to SAT….Pages 135-147
Computing the Minimal Tiling Path from a Physical Map by Integer Linear Programming….Pages 148-161
An Efficient Lagrangian Relaxation for the Contact Map Overlap Problem….Pages 162-173
A Faster Algorithm for RNA Co-folding….Pages 174-185
An Automated Combination of Kernels for Predicting Protein Subcellular Localization….Pages 186-197
Fast Target Set Reduction for Large-Scale Protein Function Prediction: A Multi-class Multi-label Machine Learning Approach….Pages 198-209
Multiple Instance Learning Allows MHC Class II Epitope Predictions Across Alleles….Pages 210-221
An Algorithm for Orienting Graphs Based on Cause-Effect Pairs and Its Applications to Orienting Protein Networks….Pages 222-232
Enumerating Precursor Sets of Target Metabolites in a Metabolic Network….Pages 233-244
Boosting the Performance of Inference Algorithms for Transcriptional Regulatory Networks Using a Phylogenetic Approach….Pages 245-258
Fast Bayesian Haplotype Inference Via Context Tree Weighting….Pages 259-270
Genotype Sequence Segmentation: Handling Constraints and Noise….Pages 271-283
Constructing Phylogenetic Supernetworks from Quartets….Pages 284-295
Summarizing Multiple Gene Trees Using Cluster Networks….Pages 296-305
Fast and Adaptive Variable Order Markov Chain Construction….Pages 306-317
Computing Alignment Seed Sensitivity with Probabilistic Arithmetic Automata….Pages 318-329
The Relation between Indel Length and Functional Divergence: A Formal Study….Pages 330-341
Detecting Repeat Families in Incompletely Sequenced Genomes….Pages 342-353
Novel Phylogenetic Network Inference by Combining Maximum Likelihood and Hidden Markov Models….Pages 354-368
A Local Move Set for Protein Folding in Triangular Lattice Models….Pages 369-381
Protein Decoy Generation Using Branch and Bound with Efficient Bounding….Pages 382-393
Back Matter….Pages –