Skip to content

Genome_Assembly_with_de_Bruijn_Graphs.md

Latest commit

 

History

History
168 lines (100 loc) · 3.53 KB

Genome_Assembly_with_de_Bruijn_Graphs.md

File metadata and controls

168 lines (100 loc) · 3.53 KB
Raw

Project: Genome Assembly with de Bruijn Graphs

Background

Modern DNA sequencing technologies do not read whole genomes at once. Instead, they produce many short DNA fragments called reads. These reads originate from an unknown longer genome and overlap with each other, but their correct order is not known.

The goal of this project is to reconstruct long contiguous sequences (contigs) from short reads using a de Bruijn graph, a standard algorithmic approach in bioinformatics.

You will implement a simplified genome assembler in F#, focusing on core algorithmic ideas rather than performance optimizations.

Learning Objectives

After completing this project, you should be able to:

  • Explain the genome assembly problem in your own words
  • Extract overlapping substrings (k-mers) from DNA reads
  • Construct a directed graph that represents sequence overlaps
  • Traverse a graph to recover contiguous DNA sequences
  • Translate a biological problem into a clear algorithmic pipeline

Problem Description

You are given a collection of DNA reads (strings consisting of A, C, G, T) and a positive integer k.

Your task is to:

  1. Break all reads into overlapping substrings of length k (k-mers)

  2. Build a directed graph where:

    • nodes are strings of length k−1
    • directed edges represent observed k-mers

  3. Extract all unitigs, i.e. maximal non-branching paths in the graph

  4. Output the corresponding DNA contig sequences

Definitions

k-mers

Given a DNA string and an integer k, a k-mer is any substring of length k.

Example for k = 3:

ATGCG → ATG, TGC, GCG

de Bruijn Graph

For each k-mer:

  • let the prefix be the first k−1 characters
  • let the suffix be the last k−1 characters
  • add a directed edge from prefix → suffix

If the same k-mer occurs multiple times, the edge should keep a count (coverage).

Unitigs

A unitig is a maximal path in the graph where:

  • every internal node has exactly one incoming edge and one outgoing edge
  • the path cannot be extended without encountering a branch

Each unitig corresponds to a contiguous DNA sequence.

Input

  • A list of DNA reads (you may assume all characters are valid)
  • An integer k ≥ 2

You may hardcode test data or read from a FASTA file.

Output

  • A list of contig sequences reconstructed from the graph
  • The output should be deterministic (e.g. sorted alphabetically)

Starting Tasks

Task 1: k-mer Extraction

Implement a function that extracts all k-mers from a DNA string.

Task 2: Graph Construction

Build the de Bruijn graph:

  • nodes: (k−1)-mers
  • edges: directed, with integer counts

Task 3: Degree Computation

For each node, compute:

  • in-degree
  • out-degree

Task 4: Unitig Extraction

Identify all maximal non-branching paths and convert them into DNA sequences.

Task 5: Output

Return all unitig sequences.

Example

Input reads

ATGC
TGCG
GCGT

k = 3

Output contig

ATGCGT

Implementation Notes

  • You may use mutable data structures if needed
  • Focus on correctness and clarity rather than performance
  • All code must be written in F#

Tasks extension

  • Filter edges with coverage below a threshold
  • Compute basic assembly statistics (number of contigs, total length)
  • Export the graph in GFA format
  • Experiment with different values of k

Submission

Submit:

  • Source code
  • A short documentation explaining your implementation
  • Test cases with expected output