Algorithms in Bioinformatics

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