+
+ /**
+ * Compute a globally optimal needleman and wunsch alignment between two
+ * sequences
+ *
+ * @param s1
+ * @param s2
+ * @param type
+ * AlignSeq.DNA or AlignSeq.PEP
+ */
+ public static AlignSeq doGlobalNWAlignment(SequenceI s1, SequenceI s2,
+ String type)
+ {
+ AlignSeq as = new AlignSeq(s1, s2, type);
+
+ as.calcScoreMatrix();
+ as.traceAlignment();
+ return as;
+ }
+
+ /**
+ *
+ * @return mapping from positions in S1 to corresponding positions in S2
+ */
+ public jalview.datamodel.Mapping getMappingFromS1(boolean allowmismatch)
+ {
+ ArrayList<Integer> as1 = new ArrayList<Integer>(),
+ as2 = new ArrayList<Integer>();
+ int pdbpos = s2.getStart() + getSeq2Start() - 2;
+ int alignpos = s1.getStart() + getSeq1Start() - 2;
+ int lp2 = pdbpos - 3, lp1 = alignpos - 3;
+ boolean lastmatch = false;
+ // and now trace the alignment onto the atom set.
+ for (int i = 0; i < astr1.length(); i++)
+ {
+ char c1 = astr1.charAt(i), c2 = astr2.charAt(i);
+ if (c1 != '-')
+ {
+ alignpos++;
+ }
+
+ if (c2 != '-')
+ {
+ pdbpos++;
+ }
+
+ // ignore case differences
+ if (allowmismatch || (c1 == c2) || (Math.abs(c2-c1)==('a'-'A')))
+ {
+ // extend mapping interval
+ if (lp1 + 1 != alignpos || lp2 + 1 != pdbpos)
+ {
+ as1.add(Integer.valueOf(alignpos));
+ as2.add(Integer.valueOf(pdbpos));
+ }
+ lastmatch = true;
+ lp1 = alignpos;
+ lp2 = pdbpos;
+ }
+ else
+ {
+ // extend mapping interval
+ if (lastmatch)
+ {
+ as1.add(Integer.valueOf(lp1));
+ as2.add(Integer.valueOf(lp2));
+ }
+ lastmatch = false;
+ }
+ }
+ // construct range pairs
+
+ int[] mapseq1 = new int[as1.size() + (lastmatch ? 1 : 0)],
+ mapseq2 = new int[as2.size() + (lastmatch ? 1 : 0)];
+ int i = 0;
+ for (Integer ip : as1)
+ {
+ mapseq1[i++] = ip;
+ }
+ ;
+ i = 0;
+ for (Integer ip : as2)
+ {
+ mapseq2[i++] = ip;
+ }
+ ;
+ if (lastmatch)
+ {
+ mapseq1[mapseq1.length - 1] = alignpos;
+ mapseq2[mapseq2.length - 1] = pdbpos;
+ }
+ MapList map = new MapList(mapseq1, mapseq2, 1, 1);
+
+ jalview.datamodel.Mapping mapping = new Mapping(map);
+ mapping.setTo(s2);
+ return mapping;
+ }
+
+ /**
+ * matches ochains against al and populates seqs with the best match between
+ * each ochain and the set in al
+ *
+ * @param ochains
+ * @param al
+ * @param dnaOrProtein
+ * @param removeOldAnnots
+ * when true, old annotation is cleared before new annotation
+ * transferred
+ * @return List<List<SequenceI> originals, List<SequenceI> replacement,
+ * List<AlignSeq> alignment between each>
+ */
+ public static List<List<? extends Object>> replaceMatchingSeqsWith(
+ List<SequenceI> seqs, List<AlignmentAnnotation> annotations,
+ List<SequenceI> ochains, AlignmentI al, String dnaOrProtein,
+ boolean removeOldAnnots)
+ {
+ List<SequenceI> orig = new ArrayList<SequenceI>(),
+ repl = new ArrayList<SequenceI>();
+ List<AlignSeq> aligs = new ArrayList<AlignSeq>();
+ if (al != null && al.getHeight() > 0)
+ {
+ ArrayList<SequenceI> matches = new ArrayList<SequenceI>();
+ ArrayList<AlignSeq> aligns = new ArrayList<AlignSeq>();
+
+ for (SequenceI sq : ochains)
+ {
+ SequenceI bestm = null;
+ AlignSeq bestaseq = null;
+ float bestscore = 0;
+ for (SequenceI msq : al.getSequences())
+ {
+ AlignSeq aseq = doGlobalNWAlignment(msq, sq, dnaOrProtein);
+ if (bestm == null || aseq.getMaxScore() > bestscore)
+ {
+ bestscore = aseq.getMaxScore();
+ bestaseq = aseq;
+ bestm = msq;
+ }
+ }
+ // System.out.println("Best Score for " + (matches.size() + 1) + " :"
+ // + bestscore);
+ matches.add(bestm);
+ aligns.add(bestaseq);
+ al.deleteSequence(bestm);
+ }
+ for (int p = 0, pSize = seqs.size(); p < pSize; p++)
+ {
+ SequenceI sq, sp = seqs.get(p);
+ int q;
+ if ((q = ochains.indexOf(sp)) > -1)
+ {
+ seqs.set(p, sq = matches.get(q));
+ orig.add(sp);
+ repl.add(sq);
+ sq.setName(sp.getName());
+ sq.setDescription(sp.getDescription());
+ Mapping sp2sq;
+ sq.transferAnnotation(sp,
+ sp2sq = aligns.get(q).getMappingFromS1(false));
+ aligs.add(aligns.get(q));
+ int inspos = -1;
+ for (int ap = 0; ap < annotations.size();)
+ {
+ if (annotations.get(ap).sequenceRef == sp)
+ {
+ if (inspos == -1)
+ {
+ inspos = ap;
+ }
+ if (removeOldAnnots)
+ {
+ annotations.remove(ap);
+ }
+ else
+ {
+ AlignmentAnnotation alan = annotations.remove(ap);
+ alan.liftOver(sq, sp2sq);
+ alan.setSequenceRef(sq);
+ sq.addAlignmentAnnotation(alan);
+ }
+ }
+ else
+ {
+ ap++;
+ }
+ }
+ if (sq.getAnnotation() != null && sq.getAnnotation().length > 0)
+ {
+ annotations.addAll(inspos == -1 ? annotations.size() : inspos,
+ Arrays.asList(sq.getAnnotation()));
+ }
+ }
+ }
+ }
+ return Arrays.asList(orig, repl, aligs);
+ }
+
+ /**
+ * compute the PID vector used by the redundancy filter.
+ *
+ * @param originalSequences
+ * - sequences in alignment that are to filtered
+ * @param omitHidden
+ * - null or strings to be analysed (typically, visible portion of
+ * each sequence in alignment)
+ * @param start
+ * - first column in window for calculation
+ * @param end
+ * - last column in window for calculation
+ * @param ungapped
+ * - if true then use ungapped sequence to compute PID
+ * @return vector containing maximum PID for i-th sequence and any sequences
+ * longer than that seuqence
+ */
+ public static float[] computeRedundancyMatrix(
+ SequenceI[] originalSequences, String[] omitHidden, int start,
+ int end, boolean ungapped)
+ {
+ int height = originalSequences.length;
+ float[] redundancy = new float[height];
+ int[] lngth = new int[height];
+ for (int i = 0; i < height; i++)
+ {
+ redundancy[i] = 0f;
+ lngth[i] = -1;
+ }
+
+ // long start = System.currentTimeMillis();
+
+ SimilarityParams pidParams = new SimilarityParams(true, true, true,
+ true);
+ float pid;
+ String seqi, seqj;
+ for (int i = 0; i < height; i++)
+ {
+
+ for (int j = 0; j < i; j++)
+ {
+ if (i == j)
+ {
+ continue;
+ }
+
+ if (omitHidden == null)
+ {
+ seqi = originalSequences[i].getSequenceAsString(start, end);
+ seqj = originalSequences[j].getSequenceAsString(start, end);
+ }
+ else
+ {
+ seqi = omitHidden[i];
+ seqj = omitHidden[j];
+ }
+ if (lngth[i] == -1)
+ {
+ String ug = AlignSeq.extractGaps(Comparison.GapChars, seqi);
+ lngth[i] = ug.length();
+ if (ungapped)
+ {
+ seqi = ug;
+ }
+ }
+ if (lngth[j] == -1)
+ {
+ String ug = AlignSeq.extractGaps(Comparison.GapChars, seqj);
+ lngth[j] = ug.length();
+ if (ungapped)
+ {
+ seqj = ug;
+ }
+ }
+ pid = (float) PIDModel.computePID(seqi, seqj, pidParams);
+
+ // use real sequence length rather than string length
+ if (lngth[j] < lngth[i])
+ {
+ redundancy[j] = Math.max(pid, redundancy[j]);
+ }
+ else
+ {
+ redundancy[i] = Math.max(pid, redundancy[i]);
+ }
+
+ }
+ }
+ return redundancy;
+ }
+
+ /**
+ * calculate the mean score of the alignment
+ * mean score is equal to the score of an alignmenet of two sequences with randomly shuffled AA sequence composited of the same AA as the two original sequences
+ *
+ */
+ public void meanScore()
+ {
+ //int length = (indelfreeAstr1.length() > indelfreeAstr2.length()) ? indelfreeAstr1.length() : indelfreeAstr2.length();
+ int length = indelfreeAstr1.length(); //both have the same length
+ //create HashMap for counting residues in each sequence
+ HashMap<Character, Integer> seq1ResCount = new HashMap<Character, Integer>();
+ HashMap<Character, Integer> seq2ResCount = new HashMap<Character, Integer>();
+
+ // for both sequences (String indelfreeAstr1 or 2) create a key for the residue and add 1 each time its encountered
+ for (char residue: indelfreeAstr1.toCharArray())
+ {
+ seq1ResCount.putIfAbsent(residue, 0);
+ seq1ResCount.replace(residue, seq1ResCount.get(residue) + 1);
+ }
+ for (char residue: indelfreeAstr2.toCharArray())
+ {
+ seq2ResCount.putIfAbsent(residue, 0);
+ seq2ResCount.replace(residue, seq2ResCount.get(residue) + 1);
+ }
+
+ // meanscore = for each residue pair get the number of appearance and add (countA * countB * pairwiseScore(AB))
+ // divide the meanscore by the sequence length afterwards
+ float _meanscore = 0;
+ for (char resA : seq1ResCount.keySet())
+ {
+ for (char resB : seq2ResCount.keySet())
+ {
+ int countA = seq1ResCount.get(resA);
+ int countB = seq2ResCount.get(resB);
+
+ float scoreAB = scoreMatrix.getPairwiseScore(resA, resB);
+
+ _meanscore += countA * countB * scoreAB;
+ }
+ }
+ _meanscore /= length;
+ this.meanScore = _meanscore;
+ }
+
+ public float getMeanScore()
+ {
+ return this.meanScore;
+ }
+
+ /**
+ * calculate the hypothetic max score using the self-alignment of the sequences
+ */
+ public void hypotheticMaxScore()
+ {
+ int _hmsA = 0;
+ int _hmsB = 0;
+ for (char residue: indelfreeAstr1.toCharArray())
+ {
+ _hmsA += scoreMatrix.getPairwiseScore(residue, residue);
+ }
+ for (char residue: indelfreeAstr2.toCharArray())
+ {
+ _hmsB += scoreMatrix.getPairwiseScore(residue, residue);
+ }
+ this.hypotheticMaxScore = (_hmsA < _hmsB) ? _hmsA : _hmsB; // take the lower self alignment
+
+ }
+
+ public int getHypotheticMaxScore()
+ {
+ return this.hypotheticMaxScore;
+ }
+
+ /**
+ * create strings based of astr1 and astr2 but without gaps
+ */
+ public void getIndelfreeAstr()
+ {
+ int n = astr1.length(); // both have the same length
+ for (int i = 0; i < n; i++)
+ {
+ if (Character.isLetter(astr1.charAt(i)) && Character.isLetter(astr2.charAt(i))) // if both sequences dont have a gap -> add to indelfreeAstr
+ {
+ this.indelfreeAstr1 += astr1.charAt(i);
+ this.indelfreeAstr2 += astr2.charAt(i);
+ }
+ }
+ }
+
+ /**
+ * calculates the overall score of the alignment
+ * preprescore = sum of all scores - all penalties
+ * if preprescore < 1 ~ alignmentScore = Float.NaN >
+ * alignmentScore = ((preprescore - meanScore) / (hypotheticMaxScore - meanScore)) * coverage
+ */
+ public void scoreAlignment() throws RuntimeException
+ {
+
+ getIndelfreeAstr();
+ meanScore();
+ hypotheticMaxScore();
+ // cannot calculate score because denominator would be zero
+ if (this.hypotheticMaxScore == this.meanScore)
+ {
+ throw new IllegalArgumentException(String.format("hypotheticMaxScore (%8.2f) == meanScore (%8.2f) - division by 0", hypotheticMaxScore, meanScore));
+ }
+ //int n = (astr1.length() > astr2.length()) ? astr1.length() : astr2.length();
+ int n = indelfreeAstr1.length();
+
+ float score = 0;
+ boolean aGapOpen = false;
+ boolean bGapOpen = false;
+ for (int i = 0; i < n; i++)
+ {
+ char char1 = indelfreeAstr1.charAt(i);
+ char char2 = indelfreeAstr2.charAt(i);
+ boolean aIsLetter = Character.isLetter(char1);
+ boolean bIsLetter = Character.isLetter(char2);
+ if (aIsLetter && bIsLetter) // if pair -> get score
+ {
+ score += scoreMatrix.getPairwiseScore(char1, char2);
+ } else if (!aIsLetter && !bIsLetter) { // both are gap -> skip
+ } else if ((!aIsLetter && aGapOpen) || (!bIsLetter && bGapOpen)) { // one side gapopen -> score - gap_extend
+ score -= GAP_EXTEND_COST;
+ } else { // no gap open -> score - gap_open
+ score -= GAP_OPEN_COST;
+ }
+ // adjust GapOpen status in both sequences
+ aGapOpen = (!aIsLetter) ? true : false;
+ bGapOpen = (!bIsLetter) ? true : false;
+ }
+
+ float preprescore = score; // if this score < 1 --> alignment score = Float.NaN
+ score = (score - this.meanScore) / (this.hypotheticMaxScore - this.meanScore);
+ int[] _max = MiscMath.findMax(new int[]{astr1.replace("-","").length(), astr2.replace("-","").length()}); // {index of max, max}
+ float coverage = (float) n / (float) _max[1]; // indelfreeAstr length / longest sequence length
+ float prescore = score; // only debug
+ score *= coverage;
+
+ System.out.println(String.format("prepre-score: %f, pre-score: %f, longlength: %d\nscore: %f, mean: %f, max: %d", preprescore, prescore, _max[1], score, this.meanScore, this.hypotheticMaxScore));
+ this.alignmentScore = (preprescore < 1) ? Float.NaN : score;
+ }