Kmers

BA3A — Generate the k-mer Composition of a String

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

# Rosalind: BA3A — Generate the k-mer Composition of a String
# https://rosalind.info/problems/ba3a/
#
# Given: An integer k and a string Text.
# Return: Composition_k(Text), the k-mers of Text in lexicographic order.

let text = "CAATCCAAC"
let k = 5

let result = kmers(dna(text), k) |> map(|km| str(km)) |> sort()

println("Result:")
result |> each(|km| println("  " + km))
println("Expected: AATCC ATCCA CAATC CCAAC TCCAA")

fn test_ba3a_kmer_composition() {
    assert len(result) == len(text) - k + 1, "BA3A: got " + str(len(result)) + " k-mers"
    let joined = result |> join(" ")
    assert joined == "AATCC ATCCA CAATC CCAAC TCCAA", "BA3A: got " + joined
}

BA1K — Generate the Frequency Array of a String

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

Indexed by PatternToNumber, so it lists every possible k-mer including those that never occur. That is what separates it from a tally.

# Rosalind: BA1K — Generate the Frequency Array of a String
# https://rosalind.info/problems/ba1k/
#
# Given: A DNA string Text and an integer k.
# Return: The frequency array of k-mers in Text.

let text = "ACGCGGCTCTGAAA"
let k = 2

# The frequency array is indexed by PatternToNumber, so it has 4^k entries and
# lists every possible k-mer in lexicographic order — including the ones that
# never occur, which is what distinguishes it from a tally.
fn base_of(symbol) {
    if symbol == "A" then 0
    else if symbol == "C" then 1
    else if symbol == "G" then 2
    else 3
}

fn pattern_to_number(pattern) {
    range(0, len(pattern)) |> reduce(|acc, i| acc * 4 + base_of(substr(pattern, i, 1)), 0)
}

let size = 1
let e = 0
while e < k {
    size = size * 4
    e = e + 1
}

let freq_array = repeat([0], size)
for i in range(0, len(text) - k + 1) {
    let index = pattern_to_number(substr(text, i, k))
    freq_array[index] = freq_array[index] + 1
}

let result = freq_array |> map(|n| str(n)) |> join(" ")

println("Result:   " + result)
println("Expected: 2 1 0 0 0 0 2 2 1 2 1 0 0 1 1 0")

fn test_ba1k_frequency_array() {
    assert result == "2 1 0 0 0 0 2 2 1 2 1 0 0 1 1 0", "BA1K: got " + result
    assert len(freq_array) == 16, "BA1K: an array of 4^k entries is expected"
    assert sum(freq_array) == len(text) - k + 1, "BA1K: counts do not add up to the windows"
}

BA1L — Implement PatternToNumber

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

k-mers in lexicographic order are the base-4 numbers with A=0, C=1, G=2, T=3.

# Rosalind: BA1L — Implement PatternToNumber
# https://rosalind.info/problems/ba1l/
#
# Given: A DNA string Pattern.
# Return: PatternToNumber(Pattern).

let pattern = "AGT"

# The k-mers in lexicographic order are the base-4 numbers, with A=0, C=1, G=2,
# T=3. So the index is just the pattern read as a number in that base.
fn base_of(symbol) {
    if symbol == "A" then 0
    else if symbol == "C" then 1
    else if symbol == "G" then 2
    else 3
}

let number = range(0, len(pattern))
  |> reduce(|acc, i| acc * 4 + base_of(substr(pattern, i, 1)), 0)

println("Result:   " + str(number))
println("Expected: 11")

fn test_ba1l_pattern_to_number() {
    assert number == 11, "BA1L: got " + str(number)
    # The first and last k-mers of length 3 anchor the range.
    assert range(0, 3) |> reduce(|a, i| a * 4 + base_of("A"), 0) == 0, "BA1L: AAA should be 0"
}

BA1M — Implement NumberToPattern

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

The inverse of BA1L.

# Rosalind: BA1M — Implement NumberToPattern
# https://rosalind.info/problems/ba1m/
#
# Given: Integers index and k.
# Return: NumberToPattern(index, k).

let index = 45
let k = 4

# The inverse of BA1L: read the index as a base-4 number, most significant digit
# first, with A=0, C=1, G=2, T=3.
let symbols = ["A", "C", "G", "T"]

let pattern = ""
let remaining = index
let position = 0
while position < k {
    let power = 1
    let e = 0
    while e < k - position - 1 {
        power = power * 4
        e = e + 1
    }
    let digit = int(remaining / power)
    pattern = pattern + symbols[digit]
    remaining = remaining - digit * power
    position = position + 1
}

println("Result:   " + pattern)
println("Expected: AGTC")

fn test_ba1m_number_to_pattern() {
    assert pattern == "AGTC", "BA1M: got " + pattern
    assert len(pattern) == k, "BA1M: wrong length"
}