Alignment and reconciliation strategies for large-scale de novo assembly

The theme of the thesis is sequencing (large) genomes and assembling them: an area at the intersection of algorithmics and technology. The birth of next-generation sequencing (NGS) and third-generation sequencing (TGS) platforms dropped the costs of genome analysis by orders of magnitude compared to the older (Sanger) method. These events also paved the way to a continuously increasing number of genome sequencing projects and the need of redesigning several algorithms (as well as data structures) in order to cope with the computational challenges introduced by the latest technologies. In this dissertation we explore two major problems: de novo assembly and long-sequence alignment. The former has been tackled, first, with a global approach and then by taking advantage of a hierarchical scheme (more natural considering the type of dataset at our disposal). More precisely, we proposed a novel assembly reconciliation tool which also proved to be competitive with state-of-the-art competitors and the only one able to scale with large datasets. The second problem analyzed, instead, has been studied in order to extend and speed up a computationally critical phase of the first one. Specifically, it consists in aligning and merging pools of long assembled sequences, each one representing a small fraction of the genome and independently assembled from NGS data. We devised a hierarchical framework (HAM) and a fingerprint-based algorithm (DFP) for merging and detecting overlaps between long and accurate sequences. Also in this case, the tools we developed achieved comparable results with state-of-the-art softwares, while using considerably less computational resources