Index of /blast-1.4/gish/dfa

      Name                    Last modified      Size  Description
      Parent Directory                             -   
      Makefile                13-Feb-1995 09:05  811   
      accepts.c               08-May-1995 09:04  1.8K  
      check.c                 08-May-1995 09:04  665   
      contains.c              08-May-1995 09:04  2.2K  
      dfa.3                   30-Sep-1998 15:55   23K  
      dfa.3.pdf               30-Sep-1998 15:55   24K  
 dfa.3.ps                30-Sep-1998 15:55   61K  
      dfa.c                   22-May-1995 10:54   30K  
      dfatest.c               08-May-1995 09:04  2.8K  
      dump.c                  22-May-1995 10:23  3.1K  
      errstr.c                08-May-1995 09:04  1.4K  
      extent.c                08-May-1995 09:04  777   
      fscanf.c                08-May-1995 09:04  601   
      libinp.msc              18-Feb-1992 10:28  154   
      makefile.msc            18-Feb-1992 10:28  1.2K  
      makefile.msw            18-Feb-1992 10:28  1.1K  
      nextstat.c              08-May-1995 09:04  946   
      opstate.c               08-May-1995 09:04  335   
      perror.c                08-May-1995 09:04  637   
      pscanf.c                08-May-1995 09:04  1.4K  
      scanf.c                 08-May-1995 09:04  654   
      size.c                  08-May-1995 09:04  951   
      sscanf.c                08-May-1995 09:04  1.4K  

This DFA (deterministic finite-state automata) function library provides a
general purpose facility for searching for one or more fixed- or
variable-length strings expressed in arbitrary, user-defined alphabets.
The computational complexity (essentially the speed) of searching for
multiple strings is the same as searching for a single string; and initial
construction of the DFA requires time and storage that are no worse than
proportional to the sum of the lengths of the strings.

The DFA library was used by early versions of BLAST (Altschul et al., 1990)
for biological sequence similarity searching.  As such, the fixed-length
words used by BLAST do not exercise the full potential of the DFA library.

For NCBI BLAST 1.4, the dfa functionality was integrated into the "gish"
library.  To compile the code, please start higher up in this directory
hierarchy at http://blast.wustl.edu/blast-1.4  Minimally one needs the
"ncbi" library and the "gish" library.  Hopefully it's not too onerous
(and oderous) a task to strip out everything else but the DFA functions
if that's all that is desired.

A variant of the DFA library is still used today in WU-BLAST 2.0.

=================================

CAVEAT EMPTOR:  the documentation file, dfa.3, a UNIX-style manual page,
has not been closely examined for consistency with the source code.

The DFA function library distribution includes the following files:

    README
    Makefile - makefile for SunOS and other UNIXes
    dfa.3 - manual page (nroff -man macros) for section 3 of the manual
    dfa.h - generally used header file
    dfa.c - core functions (dfa_new,dfa_begin,dfa_add,dfa_close)

Additional source files:

    accepts.c
    contains.c
    destruct.c
    dump.c
    check.c
    nextstat.c
    errstr.c
    extent.c
    fscanf.c
    perror.c
    pscanf.c
    scanf.c
    size.c
    sscanf.c

    dfatest.c - a small test program (not even close to being comprehensive!)

When compiling, the C preprocessor variable DFA_THENEED4SPEED can be defined
to omit some error checking for a modest improvement in execution speed.

Warren Gish
September 15, 1991