Index of /pub/blast-1.4/gish/dfa

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