W542 Nucleic Acids Research, 2005, Vol. 33, Web Server issue Figure 2. Three YASS dot-plots are shown, each obtained from pairs of closely related bacterial sequences. Green segments represent alignments of forward reads and red segments correspond to alignments between the reverse complement of one sequence and the forward read of the other. (PHP and Perl-CGI modules) on a Linux Mandrake 9.2. Dot-plots are obtained with the GD graphical library inter- faced to PHP. The YASS program has been developed in C and is distributed under the Gnu General Public License. Owing to limitations of computational resources, some restrictions have been made on the web interface. For example, uploaded ﬁles are currently limited to 3 Mb, scoring systems can be chosen only among preselected ones and for each parameter a ﬁxed range of possible values has been settled. Standalone version The standalone version is recommended for frequent users or those who need speciﬁc parameters to be set outside preselec- ted values. It provides access to two other output formats, including a BLAST-like tabular format that can be used by existing postprocessing parsers. Note that YASS does not need one of the sequences to be preprocessed ( formatdb command of BLAST), rather, it treats both sequences on the ﬂy. METHODS Seed model Here we brieﬂy outline the underlying principles of the YASS algorithm, including some novel features. For a more detailed presentation the reader is referred to (16) (http://www. biomedcentral.com/1471-2105/5/149/). Seeds are speciﬁed using a seed pattern built over a three-letter alphabet #, @ and –, where # stands for a nucleotide match, – for a don’t care symbol and @ for a match or a transition (mutation A$G or C$T). The weight of a pattern is deﬁned as the number of # plus half the number of @. The weight is the main characteristic of seed selectivity. The advantage of transition-constrained seeds stems from the biological observation that transition mutations are relat- ively more frequent than transversions, in both coding and non-coding regions. Typically, biologically relevant align- ments contain about the same number of transitions and trans- versions, whereas transitions are half as frequent in independently and identically distributed random sequences. Transition-constrained seeds increase the possible number of transitions in a hit relative to spaced seeds without the trans- ition constraint, and this is done without loss of sensitivity or efﬁciency. The sensitivity of a given seed has been estimated using the algorithm of (15), which is a generalization of the one proposed in (11). Two main alignment models have been considered: a Bernoulli model (13) assumed to simulate align- ments of non-coding DNA and a hidden Markov model (10) assumed to simulate alignments of coding DNA. By default, YASS currently uses the seed #@# – – ## – – # – ##@# of weight 9, which provides a good compromise in detecting similarities in both coding and non-coding sequences. The standalone version of YASS allows users to specify their own seeds. Several preselected seeds are provided by the YASS web interface. Hit criterion YASS is based on a multi-seed hit criterion that deﬁnes a hit as a group of closely located and possibly overlapping seeds. Two seeds belong to the same group if they occur within a bounded distance or, on the other hand, are located at close dot-plot diagonals. Distance threshold parameters are com- puted according to probabilistic sequence models taking into account substitution and indel rates, similarly to models used in (17). Note that seeds of a group are allowed to overlap. An additional group size parameter sets a lower bound on the total number of individual matches and transitions of the group. Using the group size results in a ﬂexible criterion that com- bines a guaranteed selectivity with a good sensitivity on both short and long similarities. More details on the hit criterion can be found in (16). Comparative tests To validate the better performance of transition-constrained seeds compared with ordinary spaced seeds, several compar- ative experiments have been presented in (16). Transition- constrained seeds have been shown to be more sensitive with respect to some Bernoulli and hidden Markov models of alignments of coding and non-coding DNA [Tables 1 and 2 in