Java - Nussinov algorithm

@Override

	public String getName() {

		return "Nussinov algorithm";

	}

	@Override

	protected String _run(String rnaSeq, int minLoopSize) {

		int n = rnaSeq.length();			// number of nucleotides in the sequence

		int[][] M = new int[n][n+1];		// to store costs

		int[][] D = new int[n][n];			// to store decisions

		boolean[][] B = new boolean[n][n];	// to precompute which base pairs match

		for (int i=0; i<n; i++)

			for (int j=i+1; j<n; j++)

				B[i][j] = isCompatible(rnaSeq.charAt(i), rnaSeq.charAt(j));

		// Computation of the optimal number of base-pairs

		// M(i,j) = maximum number of base pairs when folding the RNA sequence from position i to position j (both inclusive), 0 <= i < n, -1 <= j < n).

		// The range for j must include one unit less than the minimum for i, and since we cannot have negative indices, this means that we have

		// to store M(i,j) at position M[i][j+1].

		// This situation (i = j+1) represents the limit case in which we have an empty sequence. No decision has to be taken in that case

		// and hence the table D does not need a sentinel. Thus, D(i,j) is stored in D[i][j] (and the same for table B).

		//

		// base case: M(i,j) = 0 if j <= i+minloopSize

		for (int i=0; i<n; i++) {

			M[i][i] = 0;				// M(i,i-1) = 0

			for (int j=i, k=0; (k<=minLoopSize) && (j<n); j++, k++) {

				M[i][j+1] = 0;			// M(i,j) = 0;

				D[i][j] = -1;			// -1 => unpaired

			}

		}

		// general case: M(i,j) = max(M(i,j-1), max (M(i, k-1) + M(k+1,j-1) + 1 | i <= k < j-minloopSize, s_k and s_j are complementary)) if j > i+minloopSize