English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Genome assembly is a fundamental problem in Bioinformatics, requiring toreconstruct a source genome from an assembly graph built from a set of reads(short strings sequenced from the genome). A notion of genome assembly solutionis that of an arc-covering walk of the graph. Since assembly graphs admit manysolutions, the goal is to find what is definitely present in all solutions, orwhat is safe. Most practical assemblers are based on heuristics having at theircore unitigs, namely paths whose internal nodes have unit in-degree andout-degree, and which are clearly safe. The long-standing open problem offinding all the safe parts of the solutions was recently solved [RECOMB 2016]yielding a 60% increase in contig length. This safe and complete genomeassembly algorithm was followed by other works improving the time bounds, aswell as extending the results for different notions of assembly solution. Butit remained open whether one can be complete also for models of genome assemblyof practical applicability.  In this paper we present a universal framework for obtaining safe andcomplete algorithms which unify the previous results, while also allowing foreasy generalisations to assembly problems including many practical aspects.This is based on a novel graph structure, called the hydrostructure of a walk,which highlights the reachability properties of the graph from the perspectiveof the walk. The hydrostructure allows for simple characterisations of theexisting safe walks, and of their new practical versions. Almost all of ourcharacterisations are directly adaptable to optimal verification algorithms,and simple enumeration algorithms. Most of these algorithms are also improvedto optimality using an incremental computation procedure and a previous optimalalgorithm of a specific model.

The Hydrostructure: a Universal Framework for Safe and Complete Algorithms for Genome Assembly