Department of Computer Science, School of Computer Engineering, Nanyang Technological University, Singapore 639798.
Bioinformatics. 2011 Oct 1;27(19):2641-7. doi: 10.1093/bioinformatics/btr459. Epub 2011 Aug 5.
Motifs in DNA sequences often appear in degenerate form, so there has been an increased interest in computational algorithms for weak motif discovery. Probabilistic algorithms are unable to detect weak motifs while exact methods have been able to detect only short weak motifs. This article proposes an exact tree-based motif detection (TreeMotif) algorithm capable of discovering longer and weaker motifs than by the existing methods.
TreeMotif converts the graphical representation of motifs into a tree-structured representation in which a tree that branches with nodes from every sequence represents motif instances. The method of tree construction is novel to motif discovery based on graphical representation. TreeMotif is more efficient and scalable in handling longer and weaker motifs than the existing algorithms in terms of accuracy and execution time. The performances of TreeMotif were demonstrated on synthetic data as well as on real biological data.
https://sites.google.com/site/shqssw/treemotif
Supplementary data are available at Bioinformatics online.
DNA 序列中的基序经常以简并的形式出现，因此人们对用于弱基序发现的计算算法越来越感兴趣。概率算法无法检测到弱基序，而精确方法只能检测到短的弱基序。本文提出了一种精确的基于树的基序检测（TreeMotif）算法，能够比现有方法发现更长和更弱的基序。
TreeMotif 将基序的图形表示转换为树状结构表示，其中从每个序列分支的节点构成基序实例的树。这种基于图形表示的基序发现的树构建方法是新颖的。与现有的基于图形表示的基序发现算法相比，TreeMotif 在处理更长和更弱的基序时，在准确性和执行时间方面更高效、更具可扩展性。TreeMotif 的性能在合成数据和真实生物数据上得到了验证。
https://sites.google.com/site/shqssw/treemotif
补充资料可在《生物信息学》在线获取。
