Motifs

MEME — New Motif Discovery

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

Partial: no probabilistic motif discovery; finds exact shared substrings instead of a MEME position-weight motif.

# Rosalind: MEME — New Motif Discovery
# https://rosalind.info/problems/meme/
#
# Given: FASTA protein sequences sharing a common motif (length >= 20).
# Return: Regular expression for the best-scoring motif.
#
# Note: This problem requires the MEME Suite external tool.
# BioLang can find exact shared substrings but not probabilistic motifs
# with position-specific variation. We demonstrate substring search instead.

let seqs = [
    "MSNLHTHHLRLQAKLHEQHPGLHVSPFEVDFDMKAIDLLGKYNNKRGFYKTLRAVRMFMILPTAIAFFDSWTLNMDLWWCWIPVHKNPHSFLKTWSPAAGHRGWQFDHNFFKDMGHHYLDQKRALQHIRHYQHVCEDWMYRCRSIWEHTPYVSHNDLCLWMAPRPCEQMISRVSSMWTLDGFPFHFRMHYPQNHESRHGQKQPLSYNFHICDDRHFGMHFPHPQNNHQEHLSHHDCMTQVYAH",
    "MCYRMTAWSSGKQFNKGADIFRMSFDLWWCWIPVHKNPHSFLKTWSPAAGHRGWQFDHNFFKQPQHVIWNHCQPFQHQMHRNFATMDYNAHKWMLRSLAGKFLDLGYRQMSRVLQHVINATPHESYNFHAKQRLSYIPVNEKIQPQETSWQVEEPF",
    "MSHKADMRSSRKKCSIGIDLWWCWIPVHKKPHSFLKTWSPAAGHRGWQFDHNFFKALGEKVRQTEKQEYFLEKFPHHEQFMISEPQKQESRCWRAVMKPEDAYNEIQTLGKQHCHFWQRHMIFVQKGVKAVQNWLSFRYTQCPYRGSQR"
]

# Find shared substrings of length >= 20 using a simple sliding window
let min_motif = 20
let first_seq = seqs[0]
let shared = []

let i = 0
while i <= len(first_seq) - min_motif {
    let candidate = substr(first_seq, i, min_motif)
    let found_in_all = true
    for seq in seqs {
        if !(seq |> contains(candidate)) then
            found_in_all = false
    }
    if found_in_all then
        shared = shared + [candidate]
    i = i + 1
}

if len(shared) > 0 then {
    println("Shared substring(s) of length " + str(min_motif) + ":")
    # Show unique shared substrings
    let seen = []
    shared |> each(|s| {
        if !(seen |> contains(s)) then {
            println("  " + s)
            seen = seen + [s]
        }
    })
}

println("\nExpected (from MEME): DLWWCWIPVHK[NK]PHSFLKTWSPAAGHRGWQFDHNFF")
println("Note: MEME finds probabilistic motifs with position-specific variants;")
println("      BioLang finds exact shared substrings as an approximation.")

fn test_meme_shared_substrings() {
    assert len(shared) == 6, "MEME: expected 6 shared 20-mers, got " + str(len(shared))
    assert shared[0] == "PHSFLKTWSPAAGHRGWQFD", "MEME: unexpected first shared substring " + shared[0]
}