Note: Title -- Preface -- Organization -- Table of Contents -- Biomolecular Structure: RNA, Protein and Molecular Comparison -- A Worst-Case and Practical Speedup for theRNA Co-folding Problem Using theFour-{\itRussians} Idea -- Introduction -- Sankoff Algorithm for Two Sequences -- Recurrences for finding the Optimal Co-fold. -- Cofold Algorithm -- Conceptually Speeding Up the Branch_function -- Implementing the Branch Function with Table R^2 -- R^2 Table Integration into Branching -- Precomputing the R^2 Table -- Fast Cofold Algorithm -- Asymptotic Time Analysis -- Memory -- Empirical Results -- Conclusion and Future Work -- References -- Sparse Estimation for Structural Variability -- Introduction -- Related Work -- Methods -- Ensemble Construction -- Analysis of Variability Using Lasso -- Electron Density Map -- Results -- Synthetic Data -- Real Data -- Conclusions -- References -- Data Structures for Accelerating Tanimoto Queries on Real Valued Vectors -- Introduction -- Data Structures -- Experimental Setup -- Results -- Conclusion -- References -- Sparsification of RNA Structure Prediction Including Pseudoknots -- Introduction -- Sparsification of the Reeder and Giegerich algorithm -- Sparsification of the Rivas and Eddy Algorithm -- Experimental Results -- Conclusion -- References -- Prediction of RNA Secondary Structure Including Kissing Hairpin Motifs -- Introduction -- Biological Relevance of Pseudoknots in RNA Structure -- RNA Folding of Nested Structures -- Folding Pseudoknots -- Typology of Structures -- Three Strategies for Kissing Hairpin Prediction -- The Combined Power of Canonization Rules and Non-ambiguous Dynamic Programming -- Decomposition Alternatives of the Kissing Hairpin Motif -- Strategy A - An O(n^4) Time, O(n^2) Space Algorithm -- Strategy B - An O(n^4) Time, O(n^2) Space Algorithm. , Strategy C - An O(n^5) Time, O(n^2) Space Algorithm -- Algorithms -- Algorithmic Subtleties -- Pseudoknot-Recurrence of {\it pknots}RG - csrPK -- Recurrences of Strategy A - csrKH_A -- Recurrences of Strategy B - csrKH_B -- Recurrences of Strategy C - csrKH_C -- Implementation via Algebraic Dynamic Programming -- Evaluation of Strategies A, B, and C -- Conclusion -- References -- Reducing the Worst Case Running Times of a Family of RNA and CFG Problems, Using Valiant's Approach -- Introduction -- Preliminaries -- Interval and Matrix Notations -- String Notations -- The Inside Vector Multiplication Template -- Example: RNA Base-Pairing Maximization -- Inside VMT Definition -- Inside VMT Algorithm -- Additional Vector Multiplication Templates -- Outside VMT -- Multiple String VMT -- Concluding Discussion -- References -- Comparative Genomics -- Reconstruction of Ancestral Genome Subject to Whole Genome Duplication, Speciation, Rearrangement and Loss -- Introduction -- Preliminaries -- Problem Definition -- Method -- Computing Adjacency Scores -- Assembling an Pre-duplication Ancestral Genome -- Results -- Simulated Data Sets -- Comparison with the Gordon et al. Ancestor -- Conclusion -- References -- Genomic Distance with DCJ and Indels -- Introduction -- DCJ, Adjacency Graph and Indels -- Accumulating Runs with Optimal DCJ Operations -- Merging Runs in One Component -- Recombinations and the DCJ-indel Distance -- Experiments and Discussion -- References -- Listing All Sorting Reversals in Quadratic Time -- Introduction -- Background -- All Sorting Reversals -- Outline -- Ominous Substrings -- Permutation with a Single Component -- Permutations with Multiple Components -- Detecting Ominous Substrings -- The Algorithm -- Conclusions -- References -- Haplotype and Genotype Analysis -- Discovering Kinship through Small Subsets -- Introduction. , Related Work -- Preliminaries and Notation -- Forbidden Sets -- Forbidden Sets Are Triplets -- Forbidden Triplets as a Means of Finding a Partition -- Experimental Results -- Accuracy Measure -- Simulation Results -- Real Data -- Probabilistic Arguments -- A Probabilistic Model -- A Simplified Algorithm -- A Bound with Two Families -- Extending to Multiple Families -- Extending to More Robust Models -- Future Work -- References -- Fixed-Parameter Algorithm for Haplotype Inferences on General Pedigrees with Small Number of Sites -- Introduction -- Preliminaries -- Setting Up Graphs -- Pedigree Graph -- Parity-Constraint Sets -- Signed Graph -- Fixed-Parameter Algorithm -- Transforming to Bipartization by Edge Removal Problem -- FPT Algorithm for Bipartization by Edge Removal -- Conclusion -- References -- Haplotypes versus Genotypes on Pedigrees -- Introduction to Pedigree Analysis -- Pedigree Problem Formulations -- Hardness Results -- Algorithms and Accuracy of Estimates -- General Haplotype and Genotype HMMs -- Haplotype Likelihoods in Linear Time -- Results -- Discussion -- References -- Haplotype Inference on Pedigrees with Recombinations and Mutations -- Motivations -- The Computational Problem -- A Heuristic Algorithm for MCHC -- A System of Linear Equations for MCHC -- A Linear System for ZRHC -- A Linear System for MCHC -- Reducing MCHC to NCP -- The Heuristic Algorithm -- Experimental Results -- Evaluation on Random Instances -- Comparison with State-of-the-Art Methods -- Conclusion -- References -- High-throughput Data Analysis: Next Generation Sequencing and Flow Cytometry -- Identifying Rare Cell Populations in Comparative Flow Cytometry -- Introduction -- Problem Formulation -- Description of Data -- Model of the Data -- Basic Definitions -- Objectives -- Methods -- Clustering -- Pairwise Comparison: Generalized Edge Cover. , Comparing Multiple Clusters -- Results -- Clustering Results -- Pairwise Comparison Results -- Coherent Groups -- Distinctive and Common Outliers -- Probabilistic Model for Groups -- Effect of APL on Bone Marrow Cells -- References -- Fast Mapping and Precise Alignment of AB SOLiD Color Reads to Reference DNA -- Introduction -- Methods -- Sequences and Numerical Encoding -- Color Read Indexing -- Greedy Alignment between Color Read and DNA Sequence -- Statistical Alignment for Color Reads -- Likelihood and Posterior Probabilities -- Experiments -- Conclusion -- References -- Design of an Efficient Out-of-Core Read Alignment Algorithm -- Introduction -- Algorithm -- Definitions -- The Basic Sort-and-Join Method -- Sort-and-Join Method for Mapping with Errors -- Implementation of Syzygy -- Encoding, Key Generation and Other Bitwise Tricks -- Main List Data Structures -- Managing "Blowups" in the Join List -- Overlapped I/O -- Sorting -- Results and Discussion -- Conclusion -- References -- Estimation of Alternative Splicing isoform Frequencies from RNA-Seq Data -- Introduction -- Related Work -- Our Contributions -- Methods -- Read Mapping -- Finding Read-Isoform Compatibilities -- The IsoEM Algorithm -- Experimental Results -- Simulation Setup -- Comparison between Methods -- Influence of Sequencing Parameters -- Conclusions and Ongoing Work -- References -- Networks -- Improved Orientations of Physical Networks -- Introduction -- Orienting Undirected Graphs -- The Classification Process -- An Orientation Algorithm for a Single Decomposition -- Orienting Mixed Graphs -- The Approximation Algorithm -- Conclusions -- References -- Enumerating Chemical Organisations in Consistent Metabolic Networks: Complexity and Algorithms -- Introduction -- Preliminaries -- Chemical Organisations in Consistent Networks -- Enumerating Chemical Organisations. , Hitting Set Approach to Enumerate Organisations -- Conclusion -- References -- Efficient Subgraph Frequency Estimation with G-Tries -- Introduction -- Preliminaries -- Graph Terminology -- Network Motifs and Frequency Count -- Related Work -- Sampling Algorithm -- G-Tries Data Structure -- Exact Subgraph Frequency -- Uniform Sampling -- Network Motif Discovery -- Results -- Conclusion -- References -- Phylogenetics -- Accuracy Guarantees for Phylogeny Reconstruction Algorithms Based on Balanced Minimum Evolution -- Introduction -- Basics, Definitions and Notation -- Results -- Proofs -- GreedyBME -- Local Topology Search -- Conclusion -- References -- The Complexity of Inferring a Minimally Resolved Phylogenetic Supertree -- Introduction -- Our Results and Organization of the Paper -- Preliminaries -- Basic Definitions -- The Algorithm of Aho et al. ASSU81 (BUILD) -- Definition of MinRS -- Related Work -- Polynomial-Time Inapproximability of MinRS -- Exact Algorithms for MinRS -- A Brute-Force Algorithm -- An Exponential-Time Algorithm for a Restricted Case of MinRS -- Concluding Remarks -- References -- Reducing Multi-state to Binary Perfect Phylogeny with Applications to Missing, Removable, Inserted, and Deleted Data -- Introduction and Background -- Reducing k-States to Binary -- Reducing k-State Perfect Phylogeny to Binary Perfect Phylogeny with Missing Data -- Extension to k-State Perfect Phylogeny with Missing Data -- Solving the MD Problem for Arbitrary k -- Solving the CR and MDCR Problems for Arbitrary k -- Insertions and Deletions as Phylogenetic Characters -- Insertions and Deletions as Phylogenetic Characters -- References -- An Experimental Study of Quartets MaxCut and Other Supertree Methods -- Introduction -- Basics -- Performance Study -- Results -- Exploring QMC under Different Source Tree Encodings. , Comparing QMC(Exp+TSQ) to Other Supertree Methods.