Searching maximal degenerate motifs guided by a compact suffix tree.
Compared to a mismatched consensus motif, a degenerate consensus motif is more suitable for modeling position-specific variations within motifs. In the literature, the state-of-art methods using degenerate consensus motifs for de novo motif finding use a naïve enumeration algorithm, which is far from efficient. In this paper, we propose an efficient algorithm to extract maximal degenerate consensus motifs from a set of sequences based on a compact suffix tree. Our algorithm achieved a time complexity about [Formula: see text] times lower than that of a naïve enumeration, where [Formula: see text] is the average length of source sequences. To demonstrate the efficiency and effectiveness of our proposed algorithm, we applied it to finding transcription factor binding sites. It is validated on a popular benchmark proposed by Tompa. The executable files of our algorithm can be accessed through http://hpc.cs.tsinghua.edu.cn/bioinfo.
Jiang
Hongshan
H
Department of Computer Science and Technology, Institute of High Performance Computing, Tsinghua University, Beijing 100084, China. hongshan.jiang@gmail.com
Zhao
Ying
Y
Chen
Wenguang
W
Zheng
Weimin
W
D000465:Algorithms; D020816:Amino Acid Motifs; D001665:Binding Sites / Q000235:genetics; D019295:Computational Biology; D016384:Consensus Sequence; D016415:Sequence Alignment / Q000706:statistics & numerical data; D012984:Software; D014157:Transcription Factors / Q000378:metabolism
D014157:Transcription Factors