Dotplots with reverse analysis
For further references, tables and images please refer to the 'Introduction to dotplots' article on this page.
Algorithm
To identify palindromic or reverted structures it is necessary to compare the source sequences T_{1} and T_{2} and in addition the complement strand of one source sequence with one of their reverted strands R_{1} and R_{2}. In case of a genetic analysis R_{1} and R_{2} need to be the reverse complement of T_{1} and T_{2}. Although reverse accessing of symbols for literal analysis could be performed directly on source sequence T, we introduce a method using R. The advantage is found in genetic analysis, where complementary bases are initially determined once and not each time the sliding window accesses a symbol in the substring.
As sequence length is unaffected by reversion the length of T_{1} and R_{1} is m and length of T_{2} and R_{2} is n. The number of pairwise matches at an alignment position (i, j) with a given window size w is evaluated between T_{1} and T_{2 }as in identity dot plots. The number of possible alignments for T_{1} is k=mw+1 and the respective number for T_{2} is l=nw+1. Results are stored in a matrix M of size l×k. For every cell (i, j) of the matrix, with 1 ≤i ≤ l and 1 ≤ j ≤ k, substrings S_{T1,j} and S_{T2,i }are compared. Substrings S_{T1,j} and S_{T2,i} range from T_{1}[j] to T_{1}[j+w1] and T_{2}[i] to T_{2}[i+w1]. Within the window pairwise compared symbols at position p with 1 ≤ p ≤ w are addressed by T_{1}[j+p1] and T_{2}[i+p1]. Additionally, the number of matches between R_{1} and T_{2} is counted. For R_{1} alignments start from the rear end with an offset of w (Figure 5). Thus the symbol at position R_{1}[mjw+p+1] is compared with T_{2}[i+p1] and T_{1}[j+p1] with R_{2}[niw+p+1] and pairwise matches for respective substrings are counted within the range for p. The opposite tails of R_{1} and T_{2} overlap with at least w symbols, comprising the outmost meaningful comparison for the respective window size .

Figure 5: Example of dot plot creation with a window size w=4 and identification of palindromic motifs. The two source strands are found in the middle and only strands next to each other are compared. In the window, two of the four symbols match when comparing one source sequence with the reverted sequence of the second. 
In M the higher value of the two evaluated substring comparisons T_{1}/T_{2} and R_{1}/T_{2} is stored. Although different symbols are evaluated match counts at (i, j) are equal between T_{1}/R_{2} and R_{1}/T_{2}. Thus, it is just required to calculate the paired matches among substrings between the two source strands and one arbitrarily chosen source and the reverted of the other.
Source
Type t2dArrayInt = Array of Array of Integer;
Function CreateDot plotWithRev (aSequence1, aSequence2, aRevOfSeq1: String; MatchWindowSize : Integer; Var ResultMatrix : t2dArrayInt): Boolean; // The function CreateDot plotWithRev creates a matrix representing // the dot plot result of the comparison among two sequences with a // given window size including palindromic search. // (c) Dr. Jan Schulz, 1014. December 2007, www.code10.info Const aScore = 1;
Var AlignsSeq1 : Integer; AlignsSeq2 : Integer; aPosInSeq1 : Integer; LengthSeq1 : Integer; LengthSeq2 : Integer; aPosInSeq2 : Integer; aScoreCounterSeq : Integer; aScoreCounterRev : Integer; aCounter : Integer; aNormPos1 : Integer; aNormPos2 : Integer; aRevPos1 : Integer; Begin // hoping for the best we expect no errors Result := True;
// get sequence lengths LengthSeq1 := Length (aSequence1); LengthSeq2 := Length (aSequence2);
//calculate number of aligns to render AlignsSeq1 := LengthSeq1  MatchWindowSize + 1; AlignsSeq2 := LengthSeq2  MatchWindowSize + 1;
// number of both aligns must be > 0 If (AlignsSeq1 <= 0) Or (AlignsSeq2 <= 0) THen Begin // Return empty but defined ResultMatrix, notify error & terminate SetLength (ResultMatrix, 0, 0); Result := False; Exit; end;
//allocate ResultMatrix SetLength (Resultmatrix, AlignsSeq2, AlignsSeq2);
// in sequence 1 a Matchwindow will be applied back off to every position ... aPosInSeq1 := AlignsSeq1; Repeat
// same with sequence 2 aPosInSeq2 := AlignsSeq2; Repeat
//prior to every new comparison reset the variables aCounter := MatchWindowSize1; aScoreCounterSeq := 0; aScoreCounterRev := 0;
// compare all characters within the Matchwindow Repeat
// when two characters match they contribute to the results aNormPos1 := aPosInSeq1 + aCounter; aNormPos2 := aPosInSeq2 + aCounter; aRevPos1 := LengthSeq1  (aPosInSeq1 + MatchWindowSize) + aCounter + 2;
If (aSequence1 [aNormPos1] = aSequence2 [aNormPos2]) THen aScoreCounterSeq := aScoreCounterSeq + aScore; If (aRevOfSeq1 [aRevPos1] = aSequence2 [aNormPos2]) THen aScoreCounterRev := aScoreCounterRev + aScore;
// decrease the number of remaining characters to compare aCounter := aCounter  1;
Until aCounter < 0;
// after comparison we store the highest result in the array If aScoreCounterRev > aScoreCounterSeq THen aScoreCounterSeq := aScoreCounterRev;
// after comparison store result in ResultMatrix ResultMatrix [aPosInSeq2  1, aPosInSeq11] := aScoreCounterSeq;
// decrease remaining comparisons for sequence 2 with the resp. pos in the first aPosinSeq2 := aPosInSeq2  1; Until aPosInSeq2 <= 0;
//decrease the number of comparisons to be made for sequence 1 aPosinSeq1 := aPosInSeq1  1; Until aPosInSeq1 <= 0;
end;
