Note: Intro -- Preface -- Organization -- Table of Contents -- QCluster: Extending Alignment-Free Measures with Quality Values for Reads Clustering -- 1 Introduction -- 2 Previous Work on Alignment-Free Measures -- 3 Comparison of Reads with Quality Values -- 3.1 Background on Quality Values -- 3.2 New Dq-Type Statistics -- 3.3 Quality Value Redistribution -- 4 QCluster: Clustering of Reads with Dq-Type Measures -- 5 Experimental Results -- 5.1 Boosting Assembly -- 6 Conclusions -- References -- Improved Approximation for the Maximum Duo-Preservation String Mapping Problem -- 1 Introduction -- 2 Hardness of Approximation -- 3 Approximation Algorithms for max duo-preservation string mapping -- 3.1 Preliminaries -- 3.2 A 4-Approximation Algorithm for MPSM -- 3.3 An 8/5-Approximation for 2-MPSM -- 4 Some Results on 3-constrained maximum induced subgraph -- 4.1 Integrality Gap of NLP and CLP -- References -- A Faster 1.375-Approximation Algorithm for Sorting by Transpositions -- 1 Introduction -- 2 Background -- 3 Finding a (2, 2)-Sequence in Linear Time -- 4 Sufficient Extensions Using Query -- 5 Conclusion -- References -- A Generalized Cost Model for DCJ-Indel Sorting -- 1 Introduction -- 2 Preliminaries -- 3 Encoding Indels as DCJs -- 4 DCJ-Indel Sorting Genomes without Singletons -- 5 Incorporating Singletons into DCJ-Indel Sorting -- 6 Conclusion -- References -- Efficient Local Alignment Discovery amongst Noisy Long Reads -- 1 Introduction and Summary -- 2 Preliminaries: Edit Graphs, Alignments, Paths, and F.R.-Waves -- 3 Rapid Seed Detection: Concept -- 4 Rapid Seed Detection: Algorithm Engineering -- 5 Rapid Local Alignment Discovery from a Seed -- 6 Empirical Performance -- References -- Efficient Indexed Alignment of Contigs to Optical Maps -- 1 Introduction -- 2 Background -- 3 Methods -- 3.1 Converting Contigs to the Optical Map Domain. , 3.2 Building an FM-index from Optical Mapping Data -- 3.3 Alignment of Contigs Using the FM-index -- 3.4 Output of Alignments in PSL Format -- 4 Results -- 4.1 Performance on Yersinia kristensenii -- 4.2 Performance on Rice Genome -- 4.3 Performance on Budgerigar Genome -- 4.4 Alignment Verification -- 5 Discussion and Conclusions -- References -- Navigating in a Sea of Repeats in RNA-seq without Drowning -- 1 Introduction -- 2 Preliminaries -- 3 Repeats in de Bruijn Graphs -- 3.1 Simple Uniform Model for Repeats -- 3.2 Topological Characterization of the Subgraphs Generated by Repeats -- 3.3 Identifying a Repeat-Associated Subgraph -- 4 Bubbles "Drowned" in Repeats -- 4.1 Enumerating Bubbles Avoiding Repeats -- 5 Experimental Results -- 5.1 Experimental Setup -- 5.2 KsNew vs KsOld -- 5.3 KsNew vs Trinity -- 5.4 On the Usefulness of KsNew -- 6 Conclusion -- References -- Linearization of Median Genomes under DCJ -- 1 Introduction -- 2 Genome Median Problem under Various Models -- 3 Construction of Approximate Solution for L-GMP -- 3.1 Accuracy Estimation -- 3.2 Construction of Transformation T' 1 -- 4 Discussion -- References -- Appendix. An Extremal Example -- An LP-Rounding Algorithm for Degenerate Primer Design -- 1 Introduction -- 2 Related Work -- 3 Randomized Rounding -- 3.1 Randomized Rounding for Binary Strings -- 3.2 Randomized Rounding for DNA Sequences Data -- 3.3 Experimental Approximation Ratio -- 4 RRD2P - Complete Primer Design Algorithm -- 5 Experiments -- 6 Discussion -- References -- GAML: Genome Assembly by Maximum Likelihood -- 1 Introduction -- 2 Probabilistic Model for Sequence Assembly -- 3 Finding a High Likelihood Assembly -- 3.1 Optimization by Simulated Annealing -- 3.2 Preprocessing and Postprocessing -- 3.3 Fast Likelihood Evaluation -- 4 Experimental Evaluation -- 5 Conclusion -- References. , A Common Framework for Linear and Cyclic Multiple Sequence Alignment Problems -- 1 Introduction -- 2 Cyclic Multiple Alignments -- 2.1 Formal Model of Linear Sequence Alignments -- 2.2 Cyclic Orders -- 2.3 Cyclic Multiple Alignments -- 3 Partition-Based ILP for MSA and cMSA -- 4 Multiple RNA Secondary Structure Alignment -- 5 Preliminary Computational Results -- 6 Discussion -- References -- Entropic Profiles, Maximal Motifs and the Discovery of Significant Repetitions in Genomic Sequences -- 1 Introduction -- 2 Background -- 2.1 Maximal Motifs -- 2.2 Entropic Profiles -- 3 Entropic Profiles vs Maximal Motifs -- 4 Methods -- 4.1 Existing Algorithms -- 4.2 Preprocessing -- 4.3 Efficient Computation of Entropy and Normalizing Factors -- 4.4 Practical Considerations -- 5 Experimental Analysis -- 6 Concluding Remarks -- References -- Appendix -- Estimating Evolutionary Distances from Spaced-Word Matches -- 1 Introduction -- 2 Motifs and Spaced Words -- 3 The Number N of Spaced-Word Matches for a Pair of Sequences with Respect to a Set P of Patterns -- 4 Estimating Evolutionary Distances from the Number N of Spaced-Word Matches -- 5 The Variance of N -- 6 Test Results -- 7 Discussion -- References -- On the Family-Free DCJ Distance -- 1 Introduction -- 2 Preliminaries -- 2.1 Adjacency Graph and Family-Based DCJ Distance -- 2.2 Gene Similarity Graph for the Family-Free Model -- 3 Reduced Genomes and Family-Free DCJ Distance -- 3.1 The Weighted Adjacency Graph of Reduced Genomes -- 3.2 The Weighted DCJ Distance of Reduced Genomes -- 3.3 The Family-Free DCJ Distance -- 4 Complexity of the Family-Free DCJ Distance -- 5 ILP to Compute the Family-Free DCJ Distance -- 6 Conclusion -- References -- New Algorithms for Computing Phylogenetic Biodiversity -- 1 Introduction -- 2 Computing Efficiently the Variance of Known Biodiversity Measures. , 2.1 A New Algorithm for Calculating the Variance of the PD -- 2.2 Computing the Mean Nearest Taxon Distance -- 3 A New Biodiversity Measure -- 4 Experiments and Benchmarks -- References -- The Divisible Load Balance Problem and Its Application to Phylogenetic Inference -- 1 Introduction -- 2 Problem Definition -- 3 NP-hardness -- 4 Algorithm -- 5 Algorithm Analysis -- 5.1 Near-Optimal Solution -- 5.2 Run-Time -- 6 Practical Application -- 6.1 Methods -- 6.2 Results -- 7 Conclusion -- References -- Multiple Mass Spectrometry Fragmentation Trees Revisited: Boosting Performance and Quality -- 1 Introduction -- 2 Constructing Fragmentation Trees -- 3 Integer Linear Programming for Fragmentation Trees -- 3.1 ILP for Tandem MS -- 3.2 ILP for Multiple MS Allowing Transitivity Penalties Only -- 3.3 ILP for Multiple MS Using General Transitivity Scores -- 4 Correlation with Structural Similarity -- 5 Results -- 6 Conclusion -- References -- An Online Peak Extraction Algorithm for Ion Mobility Spectrometry Data -- 1 Introduction -- 2 Background -- 2.1 Data from MCC/IMS Measurements -- 2.2 Peak Modeling -- 2.3 Optimization Methods -- 3 An Algorithm for Online Peak Extraction -- 3.1 Single Spectrum Processing -- 3.2 Aligning Two Consecutive Reduced Spectra -- 3.3 Estimating 2-D Peak Models -- 4 Evaluation -- 5 Discussion and Conclusion -- References -- Best-Fit in Linear Time for Non-generative Population Simulation -- 1 Introduction -- 2 Problem 1: Deme Construction -- 3 k-CMP: Linear Algebraic Method -- 3.1 A Concrete Example -- 3 k-CMP: Linear Algebraic Method -- 4 k-CMP: Single-Step Hill Climbing -- 5 Problem 2: F1 Population with Crossover Interference -- 5.1 Background on Crossovers -- 5.2 Progeny as a 2D Matrix (Combinatorics) -- 5.3 Approximations Based on Statistical Models -- 5.4 Some Probability Calculations -- 5.5 Algorithm. , 6 Discussion and Open Problems -- References -- GDNorm: An Improved Poisson Regression Model for Reducing Biases in Hi-C Data -- 1 Introduction -- 2 Methods -- 2.1 Genomic Features -- 2.2 A Bias Correction Method Based on Gradient Descent -- 3 Experimental Results -- 3.1 Simulation Studies -- 3.2 Performance on Real Hi-C Data -- 4 Conclusion -- References -- Pacemaker Partition Identification -- 1 Introduction -- 2 The Evolutionary Model -- 3 The Pacemaker Partition Identification Procedure -- 3.1 Inferring Gene Distance -- 3.2 The Gene Correlation Graph -- 4 Simulation Analysis -- 4.1 Partition Distance -- 4.2 Simulation Results -- 5 Results on Real Data -- 6 Conclusions -- References -- Manifold de Bruijn Graphs -- 1 Introduction -- 2 From the de Bruijn Graph to the A-Bruijn Graph -- 3 From the A-Bruijn Graph to the Manifold de Bruijn Graph -- 4 Manifold de Bruijn Graphs: From a Single String to a Set of Reads -- 4.1 Consistent and Irreducible Words with Respect to a Set of Reads -- 4.2 Generalized Suffix Trees -- 5 Conclusion -- References -- Constructing String Graphs in External Memory -- 1 Introduction -- 2 Preliminaries -- 3 The Algorithm -- 4 Experimental Analysis -- 5 Conclusions and Future Work -- References -- Topology-Driven Trajectory Synthesis with an Example on Retinal Cell Motions -- 1 Introduction -- 2 Biological Background: Retinitis Pigmentosa -- 3 Synthesis Algorithm -- 4 Geometry: Pair Correlation Function -- 5 Topology: Distance of Persistence Diagrams -- 6 Experimental Results: Cone Mosaic Rearrangement -- References -- A Graph Modification Approach for Finding Core-Periphery Structures in Protein Interaction Networks -- 1 Introduction -- 2 Combinatorial Properties and Complexity -- 3 Solution Approaches -- 4 Experimental Results -- 4.1 Experimental Setup -- 4.2 Results -- 5 Outlook -- References. , Interpretable Per Case Weighted Ensemble Method for Cancer Associations.