COMP 322 Homework 3: Pairwise Sequence Alignment

Total: 100 points

Overview

Implement parallel algorithms for optimal scoring of pairwise DNA sequence alignment using the Smith-Waterman algorithm.

Testing Your Solution

# Run all tests
bin/grade workspaces/agent_hw3

# Or run specific test classes via Maven
mvn test -Dtest=Homework3Checkpoint1CorrectnessTest
mvn test -Dtest=Homework3Checkpoint2CorrectnessTest
mvn test -Dtest=Homework3Checkpoint3CorrectnessTest
mvn test -Dtest=Homework3PerformanceTest

---

Part 1: Written Assignment (30 points)

1.1 Amdahl's Law (15 points)

Consider a generalization of Amdahl's Law:

q1 = fraction of WORK that must be sequential
q2 = fraction that can use at most 2 processors
(1 - q1 - q2) = fraction that can use unbounded processors

1. (10 points) Provide the best possible upper bound on Speedup as a function of q1 and q2. 2. (5 points) Justify your answer using cases when q1=0, q2=0, q1=1, or q2=1.

1.2 Finish Accumulators (15 points)

Analyze the Parallel Search algorithm that computes Q (occurrences of pattern in text):

count0 = 0;
accumulator a = new accumulator(SUM, int.class);
finish (a) {
    for (int i = 0; i <= N - M; i++)
    async {
        int j;
        for (j = 0; j < M; j++) if (text[i+j] != pattern[j]) break;
        if (j == M) { count0++; a.put(1); }
        count1 = a.get();
    }
}
count2 = a.get();

What possible values can count0, count1, and count2 contain? Write answers in terms of M, N, and Q.

---

Part 2: Programming Assignment (70 points)

Background: Smith-Waterman Algorithm

For DNA sequences (alphabet: A, C, T, G), the Smith-Waterman algorithm computes optimal alignment scores.

Scoring scheme:

Match (p=q): +5
Mismatch (p!=q): +2
Gap in X (p,-): -4
Gap in Y (-,q): -2

Recurrence:

S[i,j] = max{
    S[i-1, j-1] + M[X[i],Y[j]],  // diagonal
    S[i-1, j] + M[X[i],-],        // gap in Y
    S[i, j-1] + M[-,Y[j]]         // gap in X
}

Boundary conditions: S[i,0] = i * M[p,-] and S[0,j] = j * M[-,q]

Checkpoint 1: IdealParScoring.java (15 points)

Maximize ideal parallelism using HJlib abstract metrics:

Insert doWork(1) for each S[i,j] computation
Do NOT use phasers
Create tasks to exploit the diagonal dependence structure

Checkpoint 2: UsefulParScoring.java (20 points)

Achieve smallest execution time on 16 cores:

Target: >= 8x speedup over sequential
Test with O(10^4) length strings
Can use phasers for synchronization

Final: SparseParScoring.java (25 points)

Sparse memory version:

Use less than O(n^2) space
Handle O(10^5) length strings
Target: >= 3x speedup

---

Key Insight

The dependence structure of S[i,j] computations forms a wavefront pattern:

Each cell depends on its left, top, and diagonal neighbors
Cells on the same anti-diagonal can be computed in parallel
This is the key to parallelization

---

Scoring

15 points: Checkpoint 1 (IdealParScoring)
20 points: Checkpoint 2 (UsefulParScoring)
25 points: Final (SparseParScoring)
10 points: Report with design, correctness justification, and performance measurements

---

Files to Implement

src/main/java/edu/rice/comp322/IdealParScoring.java
src/main/java/edu/rice/comp322/UsefulParScoring.java
src/main/java/edu/rice/comp322/SparseParScoring.java

--- *COMP 322: Fundamentals of Parallel Programming, Rice University*

AbstractDnaScoring.java2.6 KB

java

package edu.rice.comp322;

import edu.rice.hj.api.SuspendableException;

/**
 * Any method of scoring the sequential alignment of two DNA strings.
 *
 * @author Derek
 */
public abstract class AbstractDnaScoring {

    // scoring matrix
    /*
           _  A  C  G  T
        ------------------
        _ |-8 -2 -2 -2 -2
        A |-4  5  2  2  2
        C |-4  2  5  2  2
        G |-4  2  2  5  2
        T |-4  2  2  2  5
    */
    protected static final int[][] M = new int[][]{{-8, -2, -2, -2, -2},
        {-4, 5, 2, 2, 2},
        {-4, 2, 5, 2, 2},
        {-4, 2, 2, 5, 2},
        {-4, 2, 2, 2, 5}};

    /**
     * Helper method for getting the index of character in scoring matrix.
     *
     * @param inputChar The character to search for.
     * @return The index of the requested character in the matrix.
     */
    protected int charMap(final char inputChar) {
        switch (inputChar) {
            case '_':
                return 0;
            case 'A':
            case 'a':
                return 1;
            case 'C':
            case 'c':
                return 2;
            case 'G':
            case 'g':
                return 3;
            case 'T':
            case 't':
                return 4;
            default:
                throw new IllegalArgumentException("Invalid DNA character: " + inputChar);
        }
    }

    /**
     * Get score assigned for alignment of two letters.
     *
     * @param iVal the first index in the scoring matrix
     * @param jVal the second index in the scoring matrix
     * @return the corresponding value in the matrix
     */
    protected int getScore(final int iVal, final int jVal) {
        return M[iVal][jVal];
    }

    /**
     * Helper method for printing out a two dimensional int array, can be useful for debugging.
     *
     * @param matrix The desired int matrix to be printed.
     */
    public void printMatrix(final int[][] matrix) {
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                System.out.print(matrix[i][j] + " ");
            }
            System.out.println();
        }
        System.out.println("--------------------------------");
    }

    /**
     * Compute the solution matrix and return the alignment score of two DNA sequences. This one is done sequentially.
     *
     * @param x The first sequence to be compared.
     * @param y The second sequence to be compared.
     * @return The alignment score between them
     */
    public abstract int scoreSequences(String x, String y) throws SuspendableException;
}

AbstractDnaScoring.java2.6 KB

java

package edu.rice.comp322;

import edu.rice.hj.api.SuspendableException;

/**
 * Any method of scoring the sequential alignment of two DNA strings.
 *
 * @author Derek
 */
public abstract class AbstractDnaScoring {

    // scoring matrix
    /*
           _  A  C  G  T
        ------------------
        _ |-8 -2 -2 -2 -2
        A |-4  5  2  2  2
        C |-4  2  5  2  2
        G |-4  2  2  5  2
        T |-4  2  2  2  5
    */
    protected static final int[][] M = new int[][]{{-8, -2, -2, -2, -2},
        {-4, 5, 2, 2, 2},
        {-4, 2, 5, 2, 2},
        {-4, 2, 2, 5, 2},
        {-4, 2, 2, 2, 5}};

    /**
     * Helper method for getting the index of character in scoring matrix.
     *
     * @param inputChar The character to search for.
     * @return The index of the requested character in the matrix.
     */
    protected int charMap(final char inputChar) {
        switch (inputChar) {
            case '_':
                return 0;
            case 'A':
            case 'a':
                return 1;
            case 'C':
            case 'c':
                return 2;
            case 'G':
            case 'g':
                return 3;
            case 'T':
            case 't':
                return 4;
            default:
                throw new IllegalArgumentException("Invalid DNA character: " + inputChar);
        }
    }

    /**
     * Get score assigned for alignment of two letters.
     *
     * @param iVal the first index in the scoring matrix
     * @param jVal the second index in the scoring matrix
     * @return the corresponding value in the matrix
     */
    protected int getScore(final int iVal, final int jVal) {
        return M[iVal][jVal];
    }

    /**
     * Helper method for printing out a two dimensional int array, can be useful for debugging.
     *
     * @param matrix The desired int matrix to be printed.
     */
    public void printMatrix(final int[][] matrix) {
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                System.out.print(matrix[i][j] + " ");
            }
            System.out.println();
        }
        System.out.println("--------------------------------");
    }

    /**
     * Compute the solution matrix and return the alignment score of two DNA sequences. This one is done sequentially.
     *
     * @param x The first sequence to be compared.
     * @param y The second sequence to be compared.
     * @return The alignment score between them
     */
    public abstract int scoreSequences(String x, String y) throws SuspendableException;
}

Rank	Model	Score	Tests	Time	Cost
1	Claude Opus 4.6	98.8%	4/4	25m 24s	$3.92
2	Claude Sonnet 4.6	98.8%	4/4	11m 33s	$2.76
3	Claude Haiku 4.5	97.5%	4/4	25m 49s	$0.67

1

Claude Opus 4.6

98.8%

4/4 tests25.4m$3.92

2

Claude Sonnet 4.6

98.8%

4/4 tests11.6m$2.76

3

Claude Haiku 4.5

97.5%

4/4 tests25.8m$0.67