Pattern Count

Source: Dec 2024, Task 8 (DTU 02002/02003). Study solution — not an official answer key.

Problem

A DNA file contains letters A/C/G/T (line breaks are ignored). Count how many times pattern occurs, including overlaps (e.g. ACA appears twice in ACACA).

Write pattern_count(filename, pattern) returning an int.

>>> # Overlapping patterns in a string (same idea as the file task):
>>> dna = "ACACA"
>>> pattern = "ACA"
>>> sum(1 for i in range(len(dna) - len(pattern) + 1) if dna[i:i+len(pattern)] == pattern)
2
>>> # Exam example uses a file:
>>> pattern_count('files/dna_data_1.txt', 'ACCG')
2

Approach

Read the file, strip newlines into one string, then slide a window of length len(pattern) across it and count matches.

Solution

def pattern_count(filename, pattern):
    with open(filename, encoding="utf-8") as f:
        dna = "".join(line.strip() for line in f)
    count = 0
    n = len(pattern)
    for i in range(len(dna) - n + 1):
        if dna[i : i + n] == pattern:
            count += 1
    return count