Most genome rearrangements (e.g., reversals and translocations) can be represented as 2-breaks that break a genome at 2 points and glue the resulting fragments in a new order. Multi-break rearrangements break a genome into multiple fragments and further glue them together in a new order. While multi-break rearrangements were studied in depth for k=2 breaks, the k-break distance problem for arbitrary k remains unsolved. In the first part of this dissertation we address several open issues and problems related to the multi-break rearrangements : 1. We prove a duality theorem for the multi-break distance problem between circular genomes and give a polynomial algorithm for computing this distance. 2. In 2003 Pavel Pevzner and Glenn Tesler refuted the Random Breakage Model (RBM), that had been a de-facto theory of molecular evolution for more than three decades, and introduced a new Fragile Breakage Model (FBM). However, the rebuttal of RBM caused a controversy and led to a split among researchers studying genome evolution. In particular, since the mathematical theory used to refute RBM does not cover more complex rearrangement operations (like transpositions), the Pevzner--Tesler arguments do not apply for the case when transpositions are frequent. We contribute to the ongoing debates on "RBM vs. FBM" controversy by analyzing multi- break rearrangements and demonstrating that even if transpositions were a dominant force in mammalian evolution, the arguments in favor of FBM still stand. 3. We extend the above results to the more difficult case of linear genomes. In particular, we give lower bounds for the rearrangement distance between linear genomes and use these results to analyze comparative genomic architecture of mammalian genomes. In the second part of this dissertation we study rearrangements in genomes with duplicated genes. In particular, we focus on the Genome Halving Problem motivated by the whole genome duplication events in molecular evolution, first formulated and solved by Nadia El-Mabrouk and David Sankoff. We propose a new approach to analysis of rearrangements in genomes with duplicated genes, based on a generalization of conventional breakpoint graph, that let us to obtain the following results : 1. We reformulate the problem of computing the rearrangement distance between genomes with duplicated genes as two graph-theoretical problems and demonstrate how to solve their particular variants appearing in the course of solving the Genome Halving Problem. For the Genome Halving Problem with 2-breaks (i.e., standard rearrangements) this leads to an alternative short solution. 2. We further study the Genome Halving Problem with 3-breaks that add transpositions to the set of standard rearrangement operations considered by El-Mabrouk and Sankoff. The El-Mabrouk--Sankoff analysis of the 2-Break Genome Halving Problem is already rather complex making it appears unlikely that there exists a similar result for the 3-Break Genome Halving. We prove the contrary by giving a polynomial algorithm and duality theorem for the 3-Break Genome Halving Problem. 3. We reveal that while the El-Mabrouk--Sankoff analysis of the Genome Halving Problem is correct in most cases, it does not hold in the case of unichromosomal circular genomes. This raises a problem of correcting the El-Mabrouk-- Sankoff analysis and devising an algorithm that deals adequately with all genomes. We efficiently classify all genomes into two classes and show that while the El- Mabrouk--Sankoff theorem holds for the first class, it is incorrect for the second class. The crux of our analysis is a new combinatorial invariant defined on duplicated permutations. Using this invariant we were able to come up with a full proof of the Genome Halving theorem and a polynomial algorithm for the Genome Halving Problem (for unichromosomal circular genomes)

Recent advances in single-cell genomics provide an alternative to largely gene-centric metagenomics studies, enabling whole-genome sequencing of uncultivated bacteria. However, single-cell assembly projects are challenging due to (i) the highly nonuniform read coverage and (ii) a greatly elevated number of chimeric reads and read pairs. While recently developed single-cell assemblers have addressed the former challenge, methods for assembling highly chimeric reads remain poorly explored. We present algorithms for identifying chimeric edges and resolving complex bulges in de Bruijn graphs, which significantly improve single-cell assemblies. We further describe applications of the single-cell assembler SPAdes to a new approach for capturing and sequencing "microbial dark matter" that forms small pools of randomly selected single cells (called a mini-metagenome) and further sequences all genomes from the mini-metagenome at once. On single-cell bacterial datasets, SPAdes improves on the recently developed E+V-SC and IDBA-UD assemblers specifically designed for single-cell sequencing. For standard (cultivated monostrain) datasets, SPAdes also improves on A5, ABySS, CLC, EULER-SR, Ray, SOAPdenovo, and Velvet. Thus, recently developed single-cell assemblers not only enable single-cell sequencing, but also improve on conventional assemblers on their own turf. SPAdes is available for free online download under a GPLv2 license.

Variation in vectorial capacity for human malaria among Anopheles mosquito species is determined by many factors, including behavior, immunity, and life history. To investigate the genomic basis of vectorial capacity and explore new avenues for vector control, we sequenced the genomes of 16 anopheline mosquito species from diverse locations spanning ~100 million years of evolution. Comparative analyses show faster rates of gene gain and loss, elevated gene shuffling on the X chromosome, and more intron losses, relative to Drosophila. Some determinants of vectorial capacity, such as chemosensory genes, do not show elevated turnover but instead diversify through protein-sequence changes. This dynamism of anopheline genes and genomes may contribute to their flexible capacity to take advantage of new ecological niches, including adapting to humans as primary hosts.