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