Description

Source code organization

dipwmsearch implements a enumeration based strategy. In summary, it first enumerates all valid words (those words whose score are above the required score threshold), then search for occurrences of all valid words at once in the text. The two phases, enumeration and search, are separated. The search uses a classical algorithm to seek multiple words in a single text.

The source code is splitted logically in several python files. We summarize their contents and purposes here:

  1. diPwm.py : manages the class di-PWM and provides functions to compute the Look Ahead Table (LAT) or Look Ahead Matrix (LAM) of a di-PWM, to compute a score threshold from a ratio threshold or from a P-value threshold.

  2. Enumerate.py : given a di-PWM and a threshold or ratio, provides functions to enumerate all valid words using a branch-and-bound strategy combined with the LAT or LAM.

  3. AhoCorasick.py : given a di-PWM, a score or a ratio or a P-value threshold, and a sequence T, provides functions to seek the occurrences of the di-PWM in T. This function launches the enumeration of valid words (using function from Enumerate.py), builds the Aho-Corasick automaton from them, and scans the sequence T with the automaton to find all occurrences. The Aho-Corasick is a classic, linear time algorithm to search for multiple words in a text.

  4. SemiNaive.py : provides functions implementing a semi-naive search strategy consisting in scanning each window of sequence T to compute its score for the input di-PWM. It outputs all matching positions in order of appearance in T. These functions are intended for comparing the running times with those of enumeration based algorithms. It is called semi-naive for it uses the LAT or LAM to speed up the score computation of each window.

  5. Block.py : like Aho-Corasick.py but implements an optimized algorithm using what we termed the core strategy.

  6. __main__.py : this module provides a main function such that the package can also be used as a simple script. This function takes three input parameter on the command line: a file containing a di-PWM denoted P, a FASTA file containing an input sequence T, and an optional threshold ratio (in the range [0.8, 1]). It search for occurrences of P in S such that the score of a reported occurrence is greater then the threshold score computed using the input ratio. The found occurrences are reported on the standard output (and can thus be redirected into a output file). The main function controls the validity of parameters, and the search is implemented in a function called search. This function can serves as an example and easily be tailored to the user needs.