Search

Scientists routinely scan DNA sequences for transcription factor (TF) bindingsites (TFBSs). Most of the available tools rely on position-specific scoringmatrices (PSSMs) constructed from aligned binding sites. Because of theresolutions of assays used to obtain TFBSs, databases such as TRANSFAC,ORegAnno and PAZAR store unaligned variable-length DNA segments containingbinding sites of a TF. These DNA segments need to be aligned to build aPSSM. While the TRANSFAC database provides scoring matrices for TFs, nearly78% of the TFs in the public release do not have matrices available. As workon TFBS alignment algorithms has been limited, it is highly desirable tohave an alignment algorithm tailored to TFBSs. We designed a novel algorithm named LASAGNA, which is aware of the lengths ofinput TFBSs and utilizes position dependence. Results on 189 TFs of 5species in the TRANSFAC database showed that our method significantlyoutperformed ClustalW2 and MEME. We further compared a PSSM method dependenton LASAGNA to an alignment-free TFBS search method. Results on 89 TFs whosebinding sites can be located in genomes showed that our method issignificantly more precise at fixed recall rates. Finally, we describedLASAGNA-ChIP, a more sophisticated version for ChIP (Chromatinimmunoprecipitation) experiments. Under the one-per-sequence model, itshowed comparable performance with MEME in discovering motifs in ChIP-seqpeak sequences. We conclude that the LASAGNA algorithm is simple and effective in aligningvariable-length binding sites. It has been integrated into a user-friendlywebtool for TFBS search and visualization called LASAGNA-Search. The toolcurrently stores precomputed PSSM models for 189 TFs and 133 TFs built fromTFBSs in the TRANSFAC Public database (release 7.0) and the ORegAnnodatabase (08Nov10 dump), respectively. The webtool is available at http://biogrid.engr.uconn.edu/lasagna_search/ .

Identifying repeated factors that occur in a string of letters or common factors that occur in a set of strings represents an important task in computer science and biology. Such patterns are called motifs, and the process of identifying them is called motif extraction. In biology, motif extraction constitutes a fundamental step in understanding regulation of gene expression. State-of-the-art tools for motif extraction have their own constraints. Most of these tools are only designed for single motif extraction; structured motifs additionally allow for distance intervals between their single motif components. Moreover, motif extraction from large-scale datasets—for instance, large-scale ChIP-Seq datasets—cannot be performed by current tools. Other constraints include high time and/or space complexity for identifying long motifs with higher error thresholds. In this article, we introduce MoTeX-II, a word-based high-performance computing tool for structured MoTif eXtraction from large-scale datasets. Similar to its predecessor for single motif extraction, it uses state-of-the-art algorithms for solving the fixed-length approximate string matching problem. It produces similar and partially identical results to state-of-the-art tools for structured motif extraction with respect to accuracy as quantified by statistical significance measures. Moreover, we show that it matches or outperforms these tools in terms of runtime efficiency by merging single motif occurrences efficiently. MoTeX-II comes in three flavors: a standard CPU version; an OpenMP-based version; and an MPI-based version. For instance, the MPI-based version of MoTeX-II requires only a couple of hours to process all human genes for structured motif extraction on 1056 processors, while current sequential tools require more than a week for this task. Finally, we show that MoTeX-II is successful in extracting known composite transcription factor binding sites from real datasets. Use of MoTeX-II in biological frameworks may enable deriving reliable and important information since real full-length datasets can now be processed with almost any set of input parameters for both single and structured motif extraction in a reasonable amount of time. The open-source code of MoTeX-II is freely available at http://www.inf.kcl.ac.uk/research/projects/motex/ .

Background For many years now, binding preferences of Transcription Factors have been described by so called motifs, usually mathematically defined by position weight matrices or similar models, for the purpose of predicting potential binding sites. However, despite the availability of thousands of motif models in public and commercial databases, a researcher who wants to use them is left with many competing methods of identifying potential binding sites in a genome of interest and there is little published information regarding the optimality of different choices. Thanks to the availability of large number of different motif models as well as a number of experimental datasets describing actual binding of TFs in hundreds of TF-ChIP-seq pairs, we set out to perform a comprehensive analysis of this matter. Results We focus on the task of identifying potential transcription factor binding sites in the human genome. Firstly, we provide a comprehensive comparison of the coverage and quality of models available in different databases, showing that the public databases have comparable TFs coverage and better motif performance than commercial databases. Secondly, we compare different motif scanners showing that, regardless of the database used, the tools developed by the scientific community outperform the commercial tools. Thirdly, we calculate for each motif a detection threshold optimizing the accuracy of prediction. Finally, we provide an in-depth comparison of different methods of choosing thresholds for all motifs a priori. Surprisingly, we show that selecting a common false-positive rate gives results that are the least biased by the information content of the motif and therefore most uniformly accurate. Conclusion We provide a guide for researchers working with transcription factor motifs. It is supplemented with detailed results of the analysis and the benchmark datasets at http://bioputer.mimuw.edu.pl/papers/motifs/. Electronic supplementary material The online version of this article (doi:10.1186/s12859-015-0573-5) contains supplementary material, which is available to authorized users.