### grappe-3.0 README file

    README - grappe 3.0:
    ********************

    Introduction
    ************
    grappe is a pattern matching program.
    It looks, in a text, for a set of patterns containing 'don't care
    symbols' (wildcards) of unbounded or bounded length. The size of
    patterns, as well as their length, is unlimited. grappe is expected to
    be particularly efficient for searching for a big number of patterns,
    each containing don't cares. However, grappe is competitive with
    respect to other programs (egrep, agrep) on small pattern sets too.
    Patterns may occur with substitution errors. The number of errors and
    their occurrences in a pattern have to be specified by the user (this
    feature is restricted in grappe 3.0 by one error per keyword, see
    below).
    A number of other useful options are present. As an example, the user
    can specify letters occurring at a given position in a pattern by
    using multiple choice, or negation.
    A special option allows to compile a grappe version for DNA
    treatment.

    How to use grappe
    *****************
    The simplest usage of grappe is to call
      grappe <patterns> <textfile>

    <patterns> is a set of patterns specified according to the following
    syntax:
      patterns = pattern  OR pattern|patterns
      pattern  = fragment OR fragment#pattern
      fragment = keyword  OR keyword(p,q)fragment
      keyword  = word     OR keyword[set-of-letters] OR keyword[^set-of-letters] OR
                 keyword word OR ?keyword
      set-of-letters = letter   OR letter set-of-letters
      word     = letter   OR letter word

    Given a set of patterns, separated by '|' sign, grappe is looking if
    one of them (and not each of them) occurs in the text.

    Don't care symbol '#', also called unlimited (or arbitrary) wildcard,
    matches arbitrary number of caracters. Notation '(p,q)'
    (bounded-length wildcard) is used to bound the number of matched
    caracters between p and q.

    Letters in square brackets '[]' match anyone of them. If they are
    preceeded by '^' sign, this matches any other letter, i.e. anyone
    which is not listed.

    Sign '?' before a keyword means that the keyword may occur with one
    substitution error, i.e. that one letter may get replaced with respect
    to an "exact" match of the keyword.

    Note that if you wish to specify a pattern containing
    #,(,),[,],|,\,^,? then you have to protect these symbols with '\' (
    '\#', '\(', '\)', '\[', '\]', '\|', '\\', '\^', '\?' ).

    Examples
    ********
    'hello' matches any text that containing an occurence of 'hello'.
    'hello#world' matches any text containing an occurence of 'hello'
       followed, within any distance, by an occurence of 'world'.
    'hello(1,2)world' matches any text containing an occurence of 'hello'
       followed by an occurence of 'world' such that the two occurrences are
       separated by one or two letters.
    'h[ea]llo' matches any text containing an occurence of 'hello' or an
       occurence of 'hallo'.
    'h[^a]llo' matches any text containing an occurence of 'h' directly
       followed by any letter except 'a' and directly followed by an
       occurence of 'llo'. For example, 'hello' and 'hjllo' are matched.
    '?hello' matches any text containing an occurence of
       'hello' or an occurence of any subwords at a distance 1 from
       'hello'. For example, 'hello', 'hallo', 'yellow' are matched, but
       'gallo' is not matched.

    Warnings
    ********
    grappe 3.0 can handle at most one error per keyword. Besides, handling
    errors has an overhead in memory use. For some big examples, this
    memory blow-up may be prohibitive. In general, we recommend to use
    this option with the DNA version of grappe and with small keywords (of
    order of 5 letters) unless you have a lot of memory on your computer ...

    Installation
    ************
    Installing grappe is easy.
    If you got the grappe archive file which ends with gz (like
    grappe-3.0.tar.gz) you have first to decompress it with the command
       gunzip grappe-3.0.tar.gz
    Then you have to extract the archive with the command
       tar xvf grappe-3.0.tar
    Now you go to the grappe directory by typing
       cd grappe-3.0
    and then run two commands:
       ./configure
       make
    You are done.

    If you want to have a version of grappe tuned to working with DNA
    files, you type
       ./configure --enable-DNA
    instead of just ./configure. Actually, "configure" can be invoked with
    other options, to know them type
       ./configure --help

    Moreover, using "configure" allows to simply create different versions
    of grappe (for different architectures, for handling DNA files, ...)
    without duplicating source files. For exemple, you might want to
    create two versions of grappe -- generic and DNA. You may then type
    the following commands:
       mkdir generic; cd generic
       ../configure
       make
       cd ..; mkdir dna; cd dna;
       ../configure --enable-DNA
       make

    Options
    *******
    The usage of grappe is the following:
    grappe [-r] [-l] [-c] [-d <eor_chars>] ([-e] <patterns> | -f <pattern-file>) [<textfiles>]

       -r   : considers "end of record" characters as usual characters
       -l   : matches each line of the text independently
       -c   : counts the number successfully matched records (lines) of the text
       -d <separators> : redefines the "end of record" characters
                         (end-of-line by default)
       -i   : forces grappe to be case insensitive
       -e <patterns> : introduces the patterns (this option is useful when
                       the patterns begin with '-', othewise it is unnecessary).
       -f <pattern-file> : specifies the file with patterns
    You should specify exactly one set of patterns.
    If no text file is specified then grappe tries to match the
    standard input. You can specify a set of text files by listing them or
    using shell
    regular expressions. For example,
       grappe 'void' *.c
    looks for pattern 'void' in all c-files in the directory.

    DNA version
    ***********
    The DNA version of grappe understands the IUPAC nucleid acid codes in
    the patterns:
    	A = adenine
    	C = cytosine
    	G = guanine
    	T = thymine
    	U = uracil
    	R = purine	(same as [GA])
    	Y = pyrimidine	(same as [TC])
    	K = keto	(same as [GT])
    	M = amino	(same as [AC])
    	S =         	(same as [GC])
    	W =        	(same as [AT])
    	B =        	(same as [GTC])
    	D =        	(same as [GAT])
    	H =         	(same as [ACT])
    	V =         	(same as [GCA])
    	N = any 	(same as [ACGT])
    Note that the basic alphabet is {A,C,G,T,U}. 'T' and 'U' are
    synonyms. The other letters {R,Y,K,M,S,W,B,D,H,V,N} are only aliases
    to the corresponding multiple choice letter.
    Option '-i' does not work with the DNA version of grappe, which is
    **always** case insensitive and skips spaces.
    Option '-r' is not supposed to be used with the DNA version.

    Examples
    ********
    	grappe 'hello' /usr/dict/*
    	grappe -c -l 'hello' /usr/dict/words
    	grappe 'CAATCT#TATA' yeastI.pure
    	grappe -f patterns yeastI.pure

    Bug reports
    ***********
    Although we have made lots of tests in extremal conditions, bugs might
    still occur. If you happen to find one, please make a bug report to
    kucherov@loria.fr and sbriais@ens-lyon.fr, with the subject "grappe
    [Bug report]". Don't forget to indicate in your mail the command line
    that provoked the bug (in particular, send us the patterns and if
    possible the text), the type of bug (assertion failed [see note
    below], segmentation fault, ...), the computer and the operating
    system you use.
    Note that the 'assertion failed' messages of the form '.... != NULL'
    (where .... is a name of a variable) are probably out of memory
    problems and can't be fixed. Others are more interesting ...

    References
    **********
    grappe is based on the algorithm presented in the following paper:

    G. Kucherov, M. Rusinowitch
    Matching a Set of Strings with Variable Length Don't Cares
    Theoretical Computer Science, 178 (1997), pp 129-154.

    An extended abstract of this paper appeared in
    6th Symposium on Combinatorial Pattern Matching
    Helsinki, July 1995
    Lecture Notes in Computer Science, vol. 937, (1995), pp 230-247.

    You can find more informations at the following url:
    	http://www.loria.fr/~kucherov/
    or follow links from this one:
    	http://www.ens-lyon.fr/~sbriais/

    Contributors
    ************
    grappe-1  G.Kucherov (with help of P.Zimmermann and M.Rusinowitch)
    grappe-2  E.Queffelec
    grappe-3  S.Briais