Algorithms in Bioinformatics

1. Front Matter

   Pages I-XX

   PDF

2. BicNET: Efficient Biclustering of Biological Networks to Unravel Non-Trivial Modules

   • Rui Henriques, Sara C. Madeira

   Pages 1-15

3. Simultaneous Optimization of both Node and Edge Conservation in Network Alignment via WAVE

   • Yihan Sun, Joseph Crawford, Jie Tang, Tijana Milenković

   Pages 16-39

4. The Topological Profile of a Model of Protein Network Evolution Can Direct Model Improvement

   • Todd A. Gibson, Debra S. Goldberg

   Pages 40-52

5. Algorithms for Regular Tree Grammar Network Search and Their Application to Mining Human-Viral Infection Patterns

   • Ilan Smoly, Amir Carmel, Yonat Shemer-Avni, Esti Yeger-Lotem, Michal Ziv-Ukelson

   Pages 53-65

6. Orthology Relation and Gene Tree Correction: Complexity Results

   • Manuel Lafond, Nadia El-Mabrouk

   Pages 66-79

7. Finding a Perfect Phylogeny from Mixed Tumor Samples

   • Ademir Hujdurović, Urša Kačar, Martin Milanič, Bernard Ries, Alexandru I. Tomescu

   Pages 80-92

8. A Sub-quadratic Time and Space Complexity Solution for the Dated Tree Reconciliation Problem for Select Tree Topologies

   • Benjamin Drinkwater, Michael A. Charleston

   Pages 93-107

9. Maximum Parsimony Analysis of Gene Copy Number Changes

   • Jun Zhou, Yu Lin, Vaibhav Rajan, William Hoskins, Jijun Tang

   Pages 108-120

10. Multiple-Ancestor Localization for Recently Admixed Individuals

    • Yaron Margalit, Yael Baran, Eran Halperin

    Pages 121-135

11. Association Mapping for Compound Heterozygous Traits Using Phenotypic Distance and Integer Programming

    • Dan Gusfield, Rasmus Nielsen

    Pages 136-147

12. Semi-nonparametric Modeling of Topological Domain Formation from Epigenetic Data

    • Emre Sefer, Carl Kingsford

    Pages 148-161

13. Scrible: Ultra-Accurate Error-Correction of Pooled Sequenced Reads

    • Denise Duma, Francesca Cordero, Marco Beccuti, Gianfranco Ciardo, Timothy J. Close, Stefano Lonardi

    Pages 162-174

14. Jabba: Hybrid Error Correction for Long Sequencing Reads Using Maximal Exact Matches

    • Giles Miclotte, Mahdi Heydari, Piet Demeester, Pieter Audenaert, Jan Fostier

    Pages 175-188

15. Optimizing Read Reversals for Sequence Compression

    • Zhong Sichen, Lu Zhao, Yan Liang, Mohammadzaman Zamani, Rob Patro, Rezaul Chowdhury et al.

    Pages 189-202

16. Circular Sequence Comparison with q-grams

    • Roberto Grossi, Costas S. Iliopoulos, Robert Mercaş, Nadia Pisanti, Solon P. Pissis, Ahmad Retha et al.

    Pages 203-216

17. Bloom Filter Trie – A Data Structure for Pan-Genome Storage

    • Guillaume Holley, Roland Wittler, Jens Stoye

    Pages 217-230

18. A Filtering Approach for Alignment-Free Biosequences Comparison with Mismatches

    • Cinzia Pizzi

    Pages 231-242

19. Models and Algorithms for Genome Rearrangement with Positional Constraints

    • Krister M. Swenson, Mathieu Blanchette

    Pages 243-256

20. Sparse RNA Folding Revisited: Space-Efficient Minimum Free Energy Prediction

    • Sebastian Will, Hosna Jabbari

    Pages 257-270

This book constitutes the refereed proceedings of the 15th International Workshop on Algorithms in Bioinformatics, WABI 2015, held in Atlanta, GA, USA, in September 2015. The 23 full papers presented were carefully reviewed and selected from 56 submissions. The selected papers cover a wide range of topics from networks to phylogenetic studies, sequence and genome analysis, comparative genomics, and RNA structure.

• Algorithm analysis and problem complexity
• Bioinformatics
• Biological networks
• Clustering
• Complexity
• Computational biology
• Computational genomics
• Data mining
• Data structures
• Design and analysis of algorithms
• Discrete mathematics in computer science
• Evolutionary dynamics
• Genome assembly
• Genomic sequences
• Graph theory
• Knowledge discovery
• Molecular evolution
• Molecular sequence analysis
• Molecular structural biology
• Sequencing and genotyping technologies
• Protein Structure

• University of Maryland, College Park, USA

  Mihai Pop

• University of Lille, Lille, France

  Hélène Touzet

Policies and ethics