Algorithms in bioinformatics : 12th International Workshop, WABI 2012, Ljubljana, Slovenia, September 10-12, 2012 : proceedings

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. Front Matter....Pages - Preserving Inversion Phylogeny Reconstruction....Pages 1-13 Fast Phylogenetic Tree Reconstruction Using Locality-Sensitive Hashing....Pages 14-29 Efficient Computation of Popular Phylogenetic Tree Measures....Pages 30-43 SibJoin: A Fast Heuristic for Half-Sibling Reconstruction....Pages 44-56 Reconstructing the Evolution of Molecular Interaction Networks under the DMC and Link Dynamics Models....Pages 57-68 Estimating Population Size via Line Graph Reconstruction....Pages 69-80 Extracting Conflict-Free Information from Multi-labeled Trees....Pages 81-92 Reducing Problems in Unrooted Tree Compatibility to Restricted Triangulations of Intersection Graphs....Pages 93-105 An Optimal Reconciliation Algorithm for Gene Trees with Polytomies....Pages 106-122 Accounting for Gene Tree Uncertainties Improves Gene Trees and Reconciliation Inference....Pages 123-134 RNA Tree Comparisons via Unrooted Unordered Alignments....Pages 135-148 Tree Decomposition and Parameterized Algorithms for RNA Structure-Sequence Alignment Including Tertiary Interactions and Pseudoknots....Pages 149-164 δ -TRIMAX: Extracting Triclusters and Analysing Coregulation in Time Series Gene Expression Data....Pages 165-177 CLIIQ: Accurate Comparative Detection and Quantification of Expressed Isoforms in a Population....Pages 178-189 Improved Lower Bounds on the Compatibility of Quartets, Triplets, and Multi-state Characters....Pages 190-200 Succinct Multibit Tree: Compact Representation of Multibit Trees by Using Succinct Data Structures in Chemical Fingerprint Searches....Pages 201-213 Comparing DNA Sequence Collections by Direct Comparison of Compressed Text Indexes....Pages 214-224 Succinct de Bruijn Graphs....Pages 225-235 Space-Efficient and Exact de Bruijn Graph Representation Based on a Bloom Filter....Pages 236-248 From de Bruijn Graphs to Rectangle Graphs for Genome Assembly....Pages 249-261 MORPH-PRO: A Novel Algorithm and Web Server for Protein Morphing....Pages 262-273 How Accurately Can We Model Protein Structures with Dihedral Angles?....Pages 274-287 Resolving Spatial Inconsistencies in Chromosome Conformation Data....Pages 288-300 MS-DPR: An Algorithm for Computing Statistical Significance of Spectral Identifications of Non-linear Peptides....Pages 301-313 FinIS: Improved in silico Finishing Using an Exact Quadratic Programming Formulation....Pages 314-325 Lightweight LCP Construction for Next-Generation Sequencing Datasets....Pages 326-337 Sign Assignment Problems on Protein Networks....Pages 338-345 Sparse Learning Based Linear Coherent Bi-clustering....Pages 346-364 A Simplified View of DCJ-Indel Distance....Pages 365-377 DCJ-indel Distance with Distinct Operation Costs....Pages 378-390 Hidden Breakpoints in Genome Alignments....Pages 391-403 A Probabilistic Approach to Accurate Abundance-Based Binning of Metagenomic Reads....Pages 404-416 Tandem Halving Problems by DCJ....Pages 417-429 A Practical Approximation Algorithm for Solving Massive Instances of Hybridization Number....Pages 430-440 Distributed String Mining for High-Throughput Sequencing Data....Pages 441-452 Back Matter....Pages -