+ // We do not currently know the length of the alignment
+ // => Estimate it as the biggest index of a base-pair plus one.
+ int maxlength = 0;
+ for (ArrayList<SimpleBP> strs : bps)
+ {
+ for (SimpleBP bp : strs)
+ {
+
+ maxlength = Math.max(1 + Math.max(bp.bp5, bp.bp3), maxlength);
+
+ }
+ }
+ // Now we have a good estimate for length, allocate and initialize data
+ // to be fed to the dynamic programming procedure.
+ ArrayList<Hashtable<Integer, Double>> seq = new ArrayList<Hashtable<Integer, Double>>();
+ for (int i = 0; i < maxlength; i++)
+ {
+ seq.add(new Hashtable<Integer, Double>());
+ }
+ for (ArrayList<SimpleBP> strs : bps)
+ {
+ for (SimpleBP bp : strs)
+ {
+ int i = bp.bp5;
+ int j = bp.bp3;
+ Hashtable<Integer, Double> h = seq.get(i);
+ if (!h.containsKey(j))
+ {
+ h.put(j, 0.0);
+ }
+ h.put(j, h.get(j) + 1.);
+ }
+ }
+ // At this point, seq contains, at each position i, a hashtable which
+ // associates,
+ // to each possible end j, the number of time a base-pair (i,j) occurs in
+ // the alignment
+
+ // We can now run the dynamic programming procedure on this data
+ double[][] mat = fillMatrix(seq);
+ ArrayList<SimpleBP> res = backtrack(mat, seq);
+
+ // Convert it to an array, ie finalres[i] = j >= 0 iff a base-pair (i,j) is
+ // present
+ // in the consensus, or -1 otherwise
+ int[] finalres = new int[seq.size()];
+ for (int i = 0; i < seq.size(); i++)
+ {
+ finalres[i] = -1;
+ }
+ for (SimpleBP bp : res)