Name
Abstract | ||
|---|---|---|
Position weight matrices are an important method for modeling signals or motifs in biological sequences, both in DNA and protein contexts. In this paper, we present fast algorithms for the problem of finding significant matches of such matrices. Our algorithms are of the online type, and they generalize classical multipattern matching, filtering, and superalphabet techniques of combinatorial string matching to the problem of weight matrix matching. Several variants of the algorithms are developed, including multiple matrix extensions that perform the search for several matrices in one scan through the sequence database. Experimental performance evaluation is provided to compare the new techniques against each other as well as against some other online and index-based algorithms proposed in the literature. Compared to the brute-force O(mn) approach, our solutions can be faster by a factor that is proportional to the matrix length m. Our multiple-matrix filtration algorithm had the best performance in the experiments. On a current PC, this algorithm finds significant matches (p = 0.0001) of the 123 JASPAR matrices in the human genome in about 18 minutes. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1109/TCBB.2009.35 | IEEE/ACM Trans. Comput. Biology Bioinform. |
Keywords | Field | DocType |
position-specific scoring matrices,multiple matrix extension,pattern search,linear time,significant match,experimental performance evaluation,jaspar matrix,string matching.,fast algorithm,finding significant matches,best performance,weight matrix matching,position weight matrix,position weight matrices,matrix length m,classical multipattern matching,profiles,pattern matching,construction industry,indexation,bioinformatics,algorithm design and analysis,dna,string matching,automata,human genome,molecular biophysics,proteins,matched filter | String searching algorithm,Matrix (mathematics),Computer science,Artificial intelligence,Time complexity,Pattern search,Position-Specific Scoring Matrices,Sequence database,Algorithm design,Algorithm,Bioinformatics,Pattern matching,Machine learning | Journal |
Volume | Issue | ISSN |
8 | 1 | 1557-9964 |
Citations | PageRank | References |
6 | 0.50 | 21 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Cinzia Pizzi | 1 | 139 | 15.73 |
| Pasi Rastas | 2 | 57 | 7.13 |
| Esko Ukkonen | 3 | 2953 | 468.50 |