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 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 ] ([-e] | -f ) [] -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 : redefines the "end of record" characters (end-of-line by default) -i : forces grappe to be case insensitive -e : introduces the patterns (this option is useful when the patterns begin with '-', othewise it is unnecessary). -f : 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