Algorithms in Bioinformatics

by Moulton, Vincent; Singh, Mona

• ISBN13: 9783642152931
• ISBN10: 3642152937
• Edition: 1st
• Format: Paperback
• Copyright: 2010-09-27
• Publisher: Springer-Verlag New York Inc

Summary

This book constitutes the refereed proceedings of the 10th International Workshop on Algorithms in Bioinformatics, WABI 2010, held in Liverpool, UK, in September 2010.The 30 revised full papers presented were carefully reviewed and selected from 83 submissions. The papers are organized in topical sections on biomolecular structure: RNA, protein and molecular comparison; comparative genomics; haplotype and genotype analysis; high-throughput data analysis: next generation sequencing and flow cytometry; networks; phylogenetics; and sequences, strings and motifs.

Table of Contents

Biomolecular Structure: RNA, Protein and Molecular Comparison
A Worst-Case and Practical Speedup for the RNA Co-folding Problem Using the Four-Russians Idea	p. 1
Sparse Estimation for Structural Variability	p. 13
Data Structures for Accelerating Tanimoto Queries on Real Valued Vectors	p. 28
Sparsification of RNA Structure Prediction Including Pseudoknots	p. 40
Prediction of RNA Secondary Structure Including Kissing Hairpin Motifs	p. 52
Reducing the Worst Case Running Times of a Family of RNA and CFG Problems, Using Valiant's Approach	p. 65
Comparative Genomics
Reconstruction of Ancestral Genome Subject to Whole Genome Duplication, Speciation, Rearrangement and Loss	p. 78
Genomic Distance with DCJ and Indels	p. 90
Listing All Sorting Reversals in Quadratic Time	p. 102
Haplotype and Genotype Analysis
Discovering Kinship through Small Subsets	p. 111
Fixed-Parameter Algorithm for Haplotype Inferences on General Pedigrees with Small Number of Sites	p. 124
Haplotypes versus Genotypes on Pedigrees	p. 136
Haplotype Inference on Pedigrees with Recombinations and Mutations	p. 148
High-throughput Data Analysis: Next Generation Sequencing and Flow Cytometry
Identifying Rare Cell Populations in Comparative Flow Cytometry	p. 162
Fast Mapping and Precise Alignment of AB SOLiD Color Reads to Reference DNA	p. 176
Design of an Efficient Out-of-Core Read Alignment Algorithm	p. 189
Estimation of Alternative Splicing Isoform Frequencies from RNA-Seq Data	p. 202
Networks
Improved Orientations of Physical Networks	p. 215
Enumerating Chemical Organisations in Consistent Metabolic Networks: Complexity and Algorithms	p. 226
Efficient Subgraph Frequency Estimation with G-Tries	p. 238
Phylogenetics
Accuracy Guarantees for Phylogeny Reconstruction Algorithms Based on Balanced Minimum Evolution	p. 250
The Complexity of Inferring a Minimally Resolved Phylogenetic Supertree	p. 262
Reducing Multi-state to Binary Perfect Phylogeny with Applications to Missing, Removable, Inserted, and Deleted Data	p. 274
An Experimental Study of Quartets MaxCut and Other Supertree Methods	p. 288
An Efficient Method for DNA-Based Species Assignment via Gene Tree and Species Tree Reconciliation	p. 300
Sequences, Strings and Motifs
Effective Algorithms for Fusion Gene Detection	p. 312
Swiftly Computing Center Strings	p. 325
Speeding Up Exact Motif Discovery by Bounding the Expected Clump Size	p. 337
Pair HMM Based Gap Statistics for Re-evaluation of Indels in Alignments with Affine Gap Penalties	p. 350
Quantifying the Strength of Natural Selection of a Motif Sequence	p. 362
Author Index	p. 375
Table of Contents provided by Ingram. All Rights Reserved.