Jove
Visualize
Contact Us
JoVE
x logofacebook logolinkedin logoyoutube logo
ABOUT JoVE
OverviewLeadershipBlogJoVE Help Center
AUTHORS
Publishing ProcessEditorial BoardScope & PoliciesPeer ReviewFAQSubmit
LIBRARIANS
TestimonialsSubscriptionsAccessResourcesLibrary Advisory BoardFAQ
RESEARCH
JoVE JournalMethods CollectionsJoVE Encyclopedia of ExperimentsArchive
EDUCATION
JoVE CoreJoVE BusinessJoVE Science EducationJoVE Lab ManualFaculty Resource CenterFaculty Site
Terms & Conditions of Use
Privacy Policy
Policies

Related Experiment Videos

The fragment assembly string graph.

Eugene W Myers1

  • 1Department of Computer Science, University of California Berkeley, CA, USA. gene@eecs.berkeley.edu

Bioinformatics (Oxford, England)
|October 6, 2005
PubMed
Summary
This summary is machine-generated.

Related Concept Videos

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by
Same author

Complete sequencing of medaka genomes reveals the architecture of centromeric satellites, giant mobile elements, and sex chromosomes.

Genome research·2026
Same author

The genome sequence of <i>Saccopteryx leptura, Schreber, 1774</i> (Chiroptera, Emballonuridae, Saccopteryx).

Wellcome open research·2026
Same author

Evaluation of sequencing reads at scale using rdeval.

Bioinformatics (Oxford, England)·2025
Same author

Nearly T2T, phased genome assemblies of corals reveal haplotype diversity and the evolutionary process of gene expansion.

DNA research : an international journal for rapid publication of reports on genes and genomes·2025
Same author

Evaluation of sequencing reads at scale using rdeval.

bioRxiv : the preprint server for biology·2025
Same author

A chromosome-level, haplotype-resolved genome assembly and annotation for the Eurasian minnow (Leuciscidae: Phoxinus phoxinus) provide evidence of haplotype diversity.

GigaScience·2025
Same journal

3DICE: Interpretable 3D Cross-Modal Learning for Drug-Target Interaction Prediction and Large-Scale Drug Discovery.

Bioinformatics (Oxford, England)·2026
Same journal

KASSPer: Kinase Active Site Structure Prediction using Protein and Ligand Language Models and Its Application to Virtual Screening.

Bioinformatics (Oxford, England)·2026
Same journal

IDR searcher: a search engine solution for public image resources.

Bioinformatics (Oxford, England)·2026
Same journal

KCFtools: Rapid alignment-free method for introgression screening and GWAS using k-mer profiles.

Bioinformatics (Oxford, England)·2026
Same journal

Meta2DB: Curated shotgun metagenomic feature sets and metadata for health state prediction.

Bioinformatics (Oxford, England)·2026
Same journal

conMItion: an R package adjusting confounding factors for associations in multi-omics.

Bioinformatics (Oxford, England)·2026
See all related articles

We introduce the string graph, a novel method for DNA sequence assembly from shotgun sequencing reads. This approach offers efficient algorithms for constructing the graph and performing transitive reduction, proving effective for large-scale genome assembly.

Area of Science:

  • Genomics
  • Bioinformatics
  • Computational Biology

Background:

  • Shotgun sequencing generates numerous DNA fragments (reads) requiring assembly into a complete genome.
  • Existing assembly methods like de Bruijn graphs have limitations in scalability and efficiency for complex genomes.

Purpose of the Study:

  • To present a new formalism, the string graph, for representing DNA sequence information from sequencing reads.
  • To develop efficient algorithms for constructing and manipulating string graphs.
  • To demonstrate the string graph's potential for next-generation genome assembly.

Main Methods:

  • Developing a formalism called the string graph to represent all inferable information from DNA sequencing reads.
  • Implementing time and space efficient algorithms for string graph construction using read overlaps.

Related Experiment Videos

  • Presenting a novel linear expected time algorithm for transitive reduction within the string graph context.

    • Main Results:

    • The string graph effectively represents DNA sequence information from shotgun reads.
    • Efficient algorithms for string graph construction and transitive reduction have been developed.
    • The string graph approach is shown to be scalable and efficient, comparable to or exceeding existing methods.

    Conclusions:

    • The string graph formalism provides a powerful alternative to kmer-based methods like de Bruijn graphs for DNA sequence assembly.
    • The developed algorithms demonstrate the efficiency and scalability of the string graph approach.
    • This method is foundational for building advanced genome assemblers, such as BOA, capable of handling large genomes.