BLASTCLUST - BLAST score-based single-linkage clustering.

1. Clustering procedure.

BLASTCLUST automatically and systematically clusters protein or DNA sequences
based on pairwise matches found using the BLAST algorithm in case of proteins or 
Mega BLAST algorithm for DNA. In the latter case a single Mega BLAST search is
performed for all the sequences combined against a database created from the
same sequences. BLASTCLUST finds pairs of sequences that have statistically
significant matches and clusters them using single-linkage clustering. 

BLASTCLUST uses the default values for the BLAST and Mega BLAST parameters.
For protein sequences these are: matrix BLOSUM62; gap opening cost 11; gap
extension cost 1; no low-complexity filtering.
For DNA sequences: match reward 1, mismatch penalty -3, non-affine gapping costs 
(see README.mbl document for explanation), wordsize 28.
In both cases e-value threshold is set to 1e-6. 
For each pair of sequences the top-scoring alignment is evaluated according to
the following criteria: 

       x1                   x2      HSP length on seqX: Hx = x2-x1+1 
        |                    |      gaps in seqX: Gx
seqX ---======================----- seqX length: Lx
         \\|||||||||||||||||//      BLAST score: S 
seqY ----====================------ number of identical residues: N
         |                  |       seqY length: Ly
        y1                 y2       gaps in seqY: Gy
                                    HSP length on seqY: Hy = y2-y1+1 

coverage of seqX: Cx = Hx/Lx
coverage of seqY: Cy = Hy/Ly
coverage:         max(Cx,Cy) or min(Cx,Cy), depending on the value of -b option 
alignment length  Al = Hx+Gx = Hy+Gy
score density:    S/min(Hx,Hy) or N/Al*100%

If the coverage is above a certain threshold
 AND
the score density is above a certain threshold,

these two sequences are considered to be neighbored.

Thus determined neighbor relationships is considered symmetric and provides
the base for clustering by a single-linkage method (which puts a sequence
to a cluster if the sequence is a neighbor to at least one sequence in the
cluster).

2. Input formats.

The primary input format for BLASTCLUST is a FASTA-format sequence file.
Each sequence should have a unique identifier (as defined by formatdb).
BLASTCLUST formats this sequence set into a BLASTable database
(in the directory pointed to by the environment variable TMPDIR or in
the current directory), then removes the database.

Instead of a FASTA file, a database prepared by formatdb with -o option
set to TRUE can be supplied as an input.

Another type of input is a sequence hit-list previously saved by
BLASTCLUST (in this case BLASTCLUST will use pre-computed HSP data
instead of making de novo comparisons).

You can restrict clustering to a subset of your data by supplying an ID
list file (IDs separated by spaces, tabs, newlines, commas or semicolons).
This is supposed to be used for re-clustering subsets of sequences using
the previously computed hit-list file.

3. Output format.

BLASTCLUST prints out clusters of sequence IDs, sorted from largest to
smallest cluster (alphabetically by ID of the first sequence if of the
same size), separating clusters by a newline character. Sequence
identifiers within a cluster are space-separated and sorted from
longest to shortest sequence (alphabetically by IDs if of the same length).

4. Crash recovery.

If the program crashed because of system error you can restart it
using crash recovery mode. This works only if you were saving
hit-list during the clustering. Start the job with the same command
line as before, specifying the hit-list saving to the same file but
also set the "continue unfinished clustering" option to TRUE. The
process will restart from the last saved point and will append the
hit-list file.

5. Environment.

BLASTCLUST is supposed to work in a normal NCBI environment, in
particular:

BLOSUM62 matrix is available via .ncbirc or BLASTMAT environment
variable.

6. Program options

Input:

 -i <file> sequence file in the FASTA format (default = stdin)
 -d <file> sequence database name
 -r <file> name of a hit-list file saved by BLASTCLUST

 These three options are mutually exclusive.

 -l <file> a file with a list of IDs to restrict the clustering,
    applicable only when reclustering from a saved hit-list.
 
Thresholds:

 -S <threshold> similarity threshold
    if <3 then the threshold is set as a BLAST score density
    (0.0 to 3.0; default = 1.75)
    if >=3 then the threshold is set as a percent of identical
    residues (3 to 100)
 -L <threshold> minimum length coverage (0.0 to 1.0; default = 0.9)
 -b <T|F> require coverage as specified by -L and -S on both (T) or
    only one (F) sequence of a pair (default = TRUE)

Output:

 -o <file> file to save cluster list (default = stdout)
 -s <file> file to save hit-list (this file may be not portable across
    platforms)
 -p <T|F> protein (T) or nucleotide (F) sequences in the input
    (default = TRUE)

Misc:

 -C <T|F> continue unfinished clustering (crash recovery mode).
    (default = FALSE)
 -a <number> Number of CPU's to use in a multi-thread mode
    (default = 1).
 -v <logfile> Progress report destination (printed every 1000 sequences).
    Set to F to suppress report messages (default = stderr).
 -e <T|F> Enable sequence id parsing in database formatting. Set to F if 
    multiple sequences have identical ids (default = TRUE).
 -W Word size to use for initial matches (default = 0, translates to 3 for
    proteins and 32 for nucleotides). 
 -c <config file> Configuration file with advanced options, containing any 
    of the following options with their values, separated by whitespace:
    -r, -q, -G, -E - match, mismatch, gap open and gap extension scores 
respectively, 
    -e - e-value cut off,
    -y, -X - the dropoff values for the ungapped and gapped extension respectively, 
    -A - window size for two-hit version,
    -I - hitlist size,
    -Y, -z - effective search space and database length respectively, to be used for 
e-value and bit score calculations,
    -F - filter string,
    -s - raw score cut off for nucleotide search,
    -S - strand option.

7. Credits and complaints:

Ilya Dondoshansky (dondosha@ncbi.nlm.nih.gov)
Yuri Wolf (wolf@ncbi.nlm.nih.gov)

05 August, 2000

APPENDIX A.
Format of the hit-list file.

The hit-list file consists of the following parts:

 - header
 - sequence ID list
 - sequence length list
 - hit list

The byte-by-byte layout is platform-dependent; field sizes given here
are true for most UNIX platforms.

A.1. Header.

        4-byte integer  IDtype  1 if numeric IDs; 0 if string IDs
        4-byte integer  ListSz  size of the ID list; if IDs are numeric this
                                is the number of SeqID records, otherwise this
                                is the length of the ID list (in bytes)

A.2. Sequence ID list.

If IDtype is 1 (numeric IDs) then the list is ListSz records of

        4-byte integer  SeqID   sequence ID (numeric)

If IDtype is 0 (string IDs) then the list is a list of records of

        var-length char SeqID   sequence ID (string)
        space (' ')             separator

(total length is ListSz bytes; the number of sequences is equal to the number
of spaces).

A.3. Sequence length list.

This is a list of

        4-byte integer  SeqLen  sequence length

A.4. Hit list.

The list consists of the following records going to the end of file:

        4-byte integer  N1      ordinal number of the 1st sequence
        4-byte integer  N2      ordinal number of the 2nd sequence
        4-byte integer  HSPL1   HSP length on the 1st sequence
        4-byte integer  HSPL2   HSP length on the 2nd sequence
        8-byte float    Score   BLAST score
        8-byte float    PercId  Percent of identical residues