Algorithms in Bioinformatics

This book constitutes the refereed proceedings of the 12th International Workshop on Algorithms in Bioinformatics, WABI 2012, held in Ljubljana, Slovenia, in September 2012. WABI 2012 is one of six workshops which, along with the European Symposium on Algorithms (ESA), constitute the ALGO annual meeting and focuses on algorithmic advances in bioinformatics, computational biology, and systems biology with a particular emphasis on discrete algorithms and machine-learning methods that address important problems in molecular biology. The 35 full papers presented were carefully reviewed and selected from 92 submissions. The papers include algorithms for a variety of biological problems including phylogeny, DNA and RNA sequencing and analysis, protein structure, and others.

Preserving Inversion Phylogeny Reconstruction. -Fast phylogenetic tree reconstruction using locality-sensitive hashing. -Efficient Computation of Popular Phylogenetic Tree Measures. -SibJoin: A Fast Heuristic for Half-Sibling Reconstruction. -Reconstructing the Evolution of Molecular Interaction Networks under the DMC and Link Dynamics Models. -Estimating population size via line graph reconstruction. -Extracting Conflict-free Information from Multi-labeled Trees. -Reducing Problems in Unrooted Tree Compatibility to Restricted Triangulations of Intersection Graphs. -An optimal reconciliation algorithm for gene trees with polytomies. -Accounting for gene tree uncertainties improves gene trees and reconciliation inference. -RNA Tree Comparisons Via Unrooted Unordered Alignments. -Tree decomposition and parameterized algorithms for RNA structure-sequence alignment including tertiary interactions and pseudoknots (extended abstract). -CLIIQ: Accurate Comparative Detection and Quantification of Expressed Isoforms in a Population. -Improved Lower Bounds on the Compatibility of Quartets, Triplets, and Multi-State Characters.