Pintail algorithm

www.cardiff.ac.uk/biosi/research/biosoft/

Pintail: Algorithm

The Pintail algorithm is a technique for determining whether a 16S rDNA sequence is anomalous. It is based on the idea that the extent of local base differences between two aligned 16S rDNA sequences should be roughly the same along the length of the alignment (having allowed for the underlying pattern of hypervariable and conserved regions known to exist within the 16S rRNA gene). In other words, evolutionary distance between two reliable sequences should be constant along the length of the gene.

In contrast, if an error-free sequence is compared with an anomalous sequence, evolutionary distance along the alignment is unlikely to be constant, especially if the anomaly in question is a chimera and formed from phylogenetically different parental sequences.

The Pintail algorithm is designed to detect and quantify such local variations and in doing so generates the Deviation from Expectation (DE) statistic. The higher the DE value, the greater the likelihood that the query is anomalous.

The algorithm works as follows

The sequence to be checked (the query) is first globally aligned with a phylogenetically similar sequence known to be error-free (the subject). At regular intervals along the resulting alignment, the local evolutionary distance between query and subject is estimated by recording percentage base mismatches within a sampling window of fixed length. The resulting array of percentages (observed percentage differences) reflects variations in evolutionary distance between the query and subject along the length of the 16S rRNA gene. Subtracting observed percentage differences from an equivalent array of expected percentage differences (predicted values for error-free sequences), we obtain a set of deviations, the standard deviation of which (Deviation from Expectation, DE) summarises the variation between observed and expected datasets. The greater the DE value, the greater the disparity there is between observed and expected percentage differences, and the more likely it is that the query sequence is anomalous.

More formally...

Input S_q - the query sequence to be checked for anomalies.
Input S_s - the subject sequence, a reliable, error-free sequence*.
Globally align S_q with S_s to generate alignment S_qs.
Move a sampling window, of size w, b bases at a time along S_qs and at each position i determine the percentage of mismatched bases o_i within window w_i where i is 1 ≤ i ≤ n, and n is the total number of windows.
O_qs = {o_i: o₁, o₂, ..., o_n} is the set of observed percentage differences detected between S_q and S_s. The corresponding expected percentage differences E_qs {e_i: e₁, e₂, ..., e_n} are calculated from the mean of O_qs.
Subtracting e_i from o_i for each position i generates a series of deviations, the standard deviation of which quantifies the overall deviation of O_qs from E_qs. This is the Deviation from Expectation (DE) statistic.

*Note that algorithm accuracy is dependent on the choice of subject sequence. A good subject is both error-free and as evolutionary close to the query as possible. Anomalies become progressively harder to detect, the greater the overall evolutionary distance between query and subject.

The Pintail algorithm is described in Ashelford et al. (2005).