Algorithms in Bioinformatics

1. Front Matter

   PDF

2. Multichromosomal Genome Median and Halving Problems

   • Eric Tannier, Chunfang Zheng, David Sankoff

   Pages 1-13

3. A Branch-and-Bound Method for the Multichromosomal Reversal Median Problem

   • Meng Zhang, William Arndt, Jijun Tang

   Pages 14-24

4. Decompositions of Multiple Breakpoint Graphs and Rapid Exact Solutions to the Median Problem

   • Andrew Wei Xu, David Sankoff

   Pages 25-37

5. Read Mapping Algorithms for Single Molecule Sequencing Data

   • Vladimir Yanovsky, Stephen M. Rumble, Michael Brudno

   Pages 38-49

6. Exact Transcriptome Reconstruction from Short Sequence Reads

   • Vincent Lacroix, Michael Sammeth, Roderic Guigo, Anne Bergeron

   Pages 50-63

7. Post-Hybridization Quality Measures for Oligos in Genome-Wide Microarray Experiments

   • Florian Battke, Carsten Müller-Tidow, Hubert Serve, Kay Nieselt

   Pages 64-75

8. NAPX: A Polynomial Time Approximation Scheme for the Noah’s Ark Problem

   • Glenn Hickey, Paz Carmi, Anil Maheshwari, Norbert Zeh

   Pages 76-86

9. Minimum Common String Partition Parameterized

   • Peter Damaschke

   Pages 87-98

10. Hardness and Approximability of the Inverse Scope Problem

    • Zoran Nikoloski, Sergio Grimbs, Joachim Selbig, Oliver Ebenhöh

    Pages 99-112

11. Rapid Neighbour-Joining

    • Martin Simonsen, Thomas Mailund, Christian N. S. Pedersen

    Pages 113-122

12. Efficiently Computing Arbitrarily-Sized Robinson-Foulds Distance Matrices

    • Seung-Jin Sul, Grant Brammer, Tiffani L. Williams

    Pages 123-134

13. Efficient Genome Wide Tagging by Reduction to SAT

    • Arthur Choi, Noah Zaitlen, Buhm Han, Knot Pipatsrisawat, Adnan Darwiche, Eleazar Eskin

    Pages 135-147

14. Computing the Minimal Tiling Path from a Physical Map by Integer Linear Programming

    • Serdar Bozdag, Timothy J Close, Stefano Lonardi

    Pages 148-161

15. An Efficient Lagrangian Relaxation for the Contact Map Overlap Problem

    • Rumen Andonov, Nicola Yanev, Noël Malod-Dognin

    Pages 162-173

16. A Faster Algorithm for RNA Co-folding

    • Michal Ziv-Ukelson, Irit Gat-Viks, Ydo Wexler, Ron Shamir

    Pages 174-185

17. An Automated Combination of Kernels for Predicting Protein Subcellular Localization

    • Cheng Soon Ong, Alexander Zien

    Pages 186-197

18. Fast Target Set Reduction for Large-Scale Protein Function Prediction: A Multi-class Multi-label Machine Learning Approach

    • Thomas Lingner, Peter Meinicke

    Pages 198-209

19. Multiple Instance Learning Allows MHC Class II Epitope Predictions Across Alleles

    • Nico Pfeifer, Oliver Kohlbacher

    Pages 210-221

20. An Algorithm for Orienting Graphs Based on Cause-Effect Pairs and Its Applications to Orienting Protein Networks

    • Alexander Medvedovsky, Vineet Bafna, Uri Zwick, Roded Sharan

    Pages 222-232

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.

• Partition
• algorithmics
• algorithms
• approximation algorithms
• bioinformatics
• clustering
• combinatorial optimization
• completeness
• computational biology
• data analysis
• data mining
• discrete mathematics
• fingerprinting data
• functional genomics
• gene networks
• algorithm analysis and problem complexity
• data structures

Policies and ethics