DNA-Suche in C und RISC-V: Tutorial für ECE2035 Pattern Matching

Einführung in die DNA-Suche mit Pattern Matching

Die Suche nach Mustern in DNA-Sequenzen ist eine fundamentale Aufgabe der Bioinformatik und ein klassisches Programmierproblem. In diesem Tutorial lernst du, wie du einen DNA-Suchalgorithmus in C und anschließend in RISC-V Assembly implementierst – genau wie im ECE2035-Projekt 1 gefordert. Wir verwenden einen einfachen, aber effektiven Brute-Force-Ansatz, der sich hervorragend für die Übersetzung in Assembler eignet.

Warum Pattern Matching in der DNA-Analyse wichtig ist

Ob beim Erkennen von Genen, bei der Forensik oder in der personalisierten Medizin – DNA-Sequenzanalyse ist überall. Stell dir vor, du suchst nach einer bestimmten Mutation in einem langen Genom. Genau das machst du hier: Du findest alle Positionen eines kurzen DNA-Musters in einer langen Sequenz. Aktuell (Mai 2026) sind DNA-Datenbanken riesig, und effiziente Algorithmen sind gefragter denn je. In diesem Projekt lernst du die Grundlagen, die auch in modernen Bioinformatik-Tools stecken.

Das Problem verstehen: DNA-Sequenz und Muster

Eine DNA-Sequenz besteht aus den Buchstaben A, C, G, T. Deine Aufgabe ist es, ein gegebenes Muster (z.B. "GCTTTT") in der Sequenz zu finden und die Startindizes aller Vorkommen (inklusive überlappender) in einem Array zu speichern. Die Indizes müssen aufsteigend sortiert sein und mit -1 enden.

Beispiel aus der Aufgabenstellung

Sequenz: ATGACGATCTACGTATGGCAGCCACGCTTTTGATGTTA...
Muster: GCTTTT
Die erste Fundstelle ist bei Index 27. Überlappende Vorkommen zählen separat, z.B. in AAAAAA mit Muster AAA gibt es 4 Treffer bei 0,1,2,3.

Implementierung in C (P1-1)

Der Brute-Force-Ansatz

Wir durchlaufen die Sequenz Position für Position und prüfen, ob das Muster ab dieser Position übereinstimmt. Das ist einfach, aber für lange Sequenzen nicht optimal. Trotzdem ist es ein guter Ausgangspunkt.

void Match(char *pattern, int patLen, char *sequence, int seqLen) {
    int matchIndex = 0;
    for (int i = 0; i <= seqLen - patLen; i++) {
        int found = 1;
        for (int j = 0; j < patLen; j++) {
            if (sequence[i + j] != pattern[j]) {
                found = 0;
                break;
            }
        }
        if (found) {
            MatchIndices[matchIndex++] = i;
        }
    }
    MatchIndices[matchIndex] = -1;
}

Dieser Code ist selbsterklärend. Achte darauf, dass du die MatchIndices global deklarierst und die Funktion genau so implementierst, wie in der Aufgabenstellung gefordert. Verwende das bereitgestellte Shell-Programm und setze DEBUG auf 0 für die Abgabe.

Optimierungsmöglichkeiten in C

Obwohl Brute-Force funktioniert, kannst du mit kleinen Tricks die Performance verbessern. Zum Beispiel könntest du die innere Schleife früher verlassen, wenn ein Zeichen nicht passt. Oder du nutzt Zeigerarithmetik statt Indexzugriff, um die Assembly-Übersetzung zu erleichtern. Überlege auch, ob du den Pattern-Matching-Algorithmus durch Vorberechnung von Sprüngen (wie beim KMP-Algorithmus) beschleunigen könntest – aber für die Assembly-Version ist Einfachheit Trumpf.

Von C nach RISC-V: Die Übersetzung (P1-2)

RISC-V-Grundlagen für dieses Projekt

In RISC-V arbeitest du mit Registern (a0-a7, t0-t6, s0-s11, sp, ra, etc.). Die ECALLs 512, 513 und 552 helfen dir, die DNA-Sequenz zu generieren und deine Lösung zu verifizieren. Die Sequenz ist als 2-Bit-Nukleotide in 32-Bit-Wörtern gepackt. Das macht den Vergleich etwas kniffliger, aber auch effizienter.

Schritt 1: Daten laden

Du bekommst die Adressen für Muster und Sequenz via a0 und a1. Die Sequenz ist 4800 Zeichen lang, also 600 Wörter (jeweils untere 16 Bit enthalten 8 Nukleotide). Das Muster ist 3-7 Nukleotide lang und liegt als rechts-nach-links gepackte 2-Bit-Paare vor.

# Beispiel: Musterlänge laden
lw t0, 0(a2)   # t0 = Musterlänge (Annahme: a2 zeigt auf Länge)
# Hier müsstest du die tatsächlichen Parameter aus dem Shell-Programm übernehmen

Schritt 2: Äußere Schleife über die Sequenzpositionen

Du iterierst von i=0 bis (seqLen - patLen). Berechne für jede Position den Startwort- und Bit-Offset innerhalb des Wortes. Die Sequenz ist in 2-Bit-Nukleotiden gespeichert: Jedes Wort enthält 16 Nukleotide (Bits 0-15, aber eigentlich 16 Nukleotide? Nein, 16 Bit = 8 Nukleotide, da 2 Bit pro Nukleotid). Also 4800 Nukleotide = 600 Wörter (4800/8 = 600).

Schritt 3: Innerer Vergleich

Extrahiere für jede Position im Muster das entsprechende Nukleotid aus der Sequenz. Da das Muster als gepackte 2-Bit-Werte vorliegt, musst du es ebenfalls entpacken. Vergleiche jedes Nukleotid. Wenn alle übereinstimmen, speichere den Index im MatchIndices-Array.

# Pseudocode für den inneren Vergleich
# t1 = aktueller Sequenzindex i (0..4800-patLen)
# t2 = Musterlänge
# t3 = Zeiger auf MatchIndices
# t4 = matchCount
# Schleife: für j = 0 bis patLen-1
#   hole Nukleotid aus Sequenz an Position i+j
#   hole Nukleotid aus Muster an Position j
#   wenn ungleich, breche ab
# wenn alle gleich: MatchIndices[t4] = i; t4++
# nach Schleife: MatchIndices[t4] = -1

Optimierung in RISC-V

Da die Performance bewertet wird, solltest du auf folgende Punkte achten:

Minimiere die Anzahl der Befehle – verwende kurze Befehlsfolgen, vermeide unnötige Laden/Speicher-Operationen.
Nutze Register effizient – lege häufig verwendete Werte in temporären Registern ab.
Verwende Shift-Operationen für den Zugriff auf die 2-Bit-Nukleotide.
Vermeide Divisionen – nutze stattdessen Bitmasken und Shifts.

Häufige Fehler und wie du sie vermeidest

Überlappende Vorkommen ignorieren: Denke daran, dass du nach jedem Match nur um eine Position weiterschiebst, nicht um die Musterlänge.
Array-Grenzen: Das MatchIndices-Array hat Platz für 128 Einträge (plus -1). Stelle sicher, dass du nicht überschreibst.
Endianness und Bit-Reihenfolge: Die Nukleotide sind in den Wörtern von rechts nach links gepackt (LSB zuerst). Teste mit einfachen Beispielen.
ECALL-Aufruf: Vergiss nicht, ecall 513 am Ende aufzurufen, um deine Lösung zu verifizieren.

Zusammenfassung und nächste Schritte

Mit diesem Tutorial hast du eine solide Grundlage für die Implementierung des DNA-Suchalgorithmus in C und RISC-V. Der Schlüssel zum Erfolg liegt im Verständnis der Bit-Manipulation und der sauberen Übersetzung von C nach Assembly. Nutze die bereitgestellten Shell-Programme und teste deine Lösung mit verschiedenen Mustern und Sequenzen. Viel Erfolg bei deinem ECE2035-Projekt!