Graphs

2 problems from Rosalind — Bioinformatics Stronghold. Press Run on any block to execute it in your browser.

GRPH — Overlap Graphs

solvedbrowser + CLI Problem statement Open in the workbench Download .bl

Overlap graphs make reads the nodes, which makes assembly a Hamiltonian path — NP-hard. DBRU makes reads the edges instead and gets an Eulerian path, solvable in linear time. Same data, different graph, and the whole reason modern assemblers use de Bruijn graphs.

# Rosalind: GRPH — Overlap Graphs
# https://rosalind.info/problems/grph/
#
# Given: A collection of DNA strings in FASTA format.
# Return: The adjacency list of the overlap graph O(3), where an edge s -> t
# means the last 3 characters of s equal the first 3 of t, and s != t.

let k = 3
let records = [
    { id: "Rosalind_0498", seq: "AAATAAA" },
    { id: "Rosalind_2391", seq: "AAATTTT" },
    { id: "Rosalind_2323", seq: "TTTTCCC" },
    { id: "Rosalind_0442", seq: "AAATCCC" },
    { id: "Rosalind_5013", seq: "GGGTGGG" }
]

fn suffix_of(s, width) { substr(s, len(s) - width, width) }
fn prefix_of(s, width) { substr(s, 0, width) }

let edge_list = records |> flat_map(|a| {
    records
        |> filter(|b| a.id != b.id and suffix_of(a.seq, k) == prefix_of(b.seq, k))
        |> map(|b| a.id ++ " " ++ b.id)
})

println("Result:")
edge_list |> each(|e| println("  " + e))
println("Expected: 3 edge_list — 0498->2391, 0498->0442, 2391->2323")

fn test_grph_overlap_graph() {
    assert len(edge_list) == 3, "GRPH: got " + str(len(edge_list)) + " edge_list"
    assert edge_list |> contains("Rosalind_0498 Rosalind_2391"), "GRPH: missing 0498->2391"
    assert edge_list |> contains("Rosalind_0498 Rosalind_0442"), "GRPH: missing 0498->0442"
    assert edge_list |> contains("Rosalind_2391 Rosalind_2323"), "GRPH: missing 2391->2323"
}

DBRU — Constructing a De Bruijn Graph

solvedbrowser + CLI Problem statement Open in the workbench Download .bl

Reads become edges rather than nodes, which turns assembly from a Hamiltonian path problem into an Eulerian one. GRPH shows the alternative; this is the construction real assemblers are built on.

# Rosalind: DBRU — Constructing a De Bruijn Graph
# https://rosalind.info/problems/dbru/
#
# Given: A collection of up to 1000 DNA strings of equal length, all distinct.
# Return: The adjacency list of the De Bruijn graph on S union S_rc, where each
# k-mer contributes an edge from its prefix to its suffix.

let reads = ["TGAT", "CATG", "TCAT", "ATGC", "CATC", "CATC"]

# The graph is built on the reads together with their reverse complements,
# as a set — the duplicate CATC and the shared CATG collapse.
let with_reverse = reads |> flat_map(|r| [r, str(reverse_complement(dna(r)))]) |> unique()

let edge_list = with_reverse
    |> map(|kmer| substr(kmer, 0, len(kmer) - 1) ++ " -> " ++ substr(kmer, 1, len(kmer) - 1))
    |> unique()
    |> sort()

println("Result:   " + str(len(edge_list)) + " edge_list")
edge_list |> each(|e| println("  (" + replace(e, " -> ", ", ") + ")"))
println("Expected: 9 edge_list, starting (ATC, TCA) (ATG, TGA) (ATG, TGC)")

fn test_dbru_de_bruijn_graph() {
    assert len(edge_list) == 9, "DBRU: got " + str(len(edge_list))
    assert edge_list[0] == "ATC -> TCA", "DBRU: first edge " + edge_list[0]
    assert edge_list |> contains("GCA -> CAT"), "DBRU: missing GCA -> CAT"
    assert edge_list |> contains("TGA -> GAT"), "DBRU: missing TGA -> GAT"
}