title: Searching maximal degenerate motifs guided by a compact suffix tree.
abstract: 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.
authors.affiliation: Department of Computer Science and Technology, Institute of High Performance Computing, Tsinghua University, Beijing 100084, China. hongshan.jiang@gmail.com
authors.forename: Hongshan
authors.initials: H
authors.lastname: Jiang
authors.forename: Ying
authors.initials: Y
authors.lastname: Zhao
authors.forename: Wenguang
authors.initials: W
authors.lastname: Chen
authors.forename: Weimin
authors.initials: W
authors.lastname: Zheng
mesh_terms: 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
chemical_list: D014157:Transcription Factors