The fragment assembly string graph

By Eugene W. Myers. ECCB/JBI, 2005

462 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Information Systems, Molecular Biology

View Paper: https://www.semanticscholar.org/paper/e15ad6b7fc692aaa5855691599e263a600d85325

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Information Systems

In Molecular Biology

Citations in the corpus

Canu: scalable and accurate long-read assembly via adaptive k-mer weighting and repeat separation (2016, background): “Instead, Miniasm generates a string graph (Myers 2005) directly from approximate read overlaps and labels the edges of this graph with the raw read sequences.”
Minimus: a fast, lightweight genome assembler (2007, methodology): “2. tigger – a unitigger, i.e. tool that identifies clusters of reads which can be uniquely assembled based on algorithms developed by Myers [28,29]; in graph theoretic terms a unitigger identifies maximal interval subgraphs of the overlap graph.”
De novo bacterial genome sequencing: millions of very short reads assembled on a desktop computer. (2008, methodology): “This application is based on a k -mer graph representation (Idury and Waterman 1995; Pevzner et al. 2001) that structures all k -mers observed in the reads.”
Exploring single-sample SNP and INDEL calling with whole-genome de novo assembly (2012, background): “ABSTRACT Motivation: Eugene Myers in his string graph paper (Myers, 2005)”
IDBA - A Practical Iterative de Bruijn Graph De Novo Assembler (2010, background): “String graph algorithms [9, 14] represent each read by a vertex and there is a directed edge from vertex u to vertex v if the suffix of at least x nucleotides of read u is the same as the prefix of read v.”
The complete sequence of a human genome (2021, background): “To enable assembly of the highly repetitive centromeric satellite arrays and closely related segmentalduplications,wedevelopedmethods Table 1.”
Assembly Algorithms for Next-Generation Sequencing Data (2010, unknown): “Network flowanalysis has been described for resolution of repeat copy number during genome assembly [52,66].”
A Primer on Metagenomics (2010, background): “). Other variations have since been published, adapting to short (100–200)”
Comparing and Evaluating Metagenome Assembly Tools from a Microbiologist’s Perspective - Not Only Size Matters! (2017, methodology): “By employing the string graph approach [49] it can cope with short Illumina read lengths and the related repeat resolution problems in a similar way as de Bruijn graph approaches, but with the advantage of preserving the complete sequence context information for every read.”
Oases: robust de novo RNA-seq assembly across the dynamic range of expression levels (2012, methodology): “Scaffold construction takes place in two stages similarly to the approach described by Butler et al. (2008).”
Genome assembly reborn: recent computational challenges (2009, methodology): “In fact, simple transformations of the overlap graph from the OLC paradigm leads to a graph structure (string graph) that is functionally equivalent to the deBruijn graph of a genome [33], hinting at the equivalence between these assembly paradigms.”
Velvet: algorithms for de novo short read assembly using de Bruijn graphs. (2008, methodology): “The simplification of two nodes into one is analogous to the conventional concatenation of two character strings, and also to some string graph based methods (Myers 2005).”
Piercing the dark matter: bioinformatics of long-range sequencing and mapping (2018, methodology): “The FALCON assembler and the new MARVEL assembler for PacBio reads operate similarly to Canu, although they both use DALIGNER 43 instead of MHAP to compute the overlaps between reads for error correction and assembly, and form a string graph 44 rather than an overlap graph.”