TY - GEN
T1 - Efficient algorithms for model-based motif discovery from multiple sequences
AU - Fu, Bin
AU - Kao, Ming-Yang
AU - Wang, Lusheng
N1 - Copyright:
Copyright 2021 Elsevier B.V., All rights reserved.
PY - 2008
Y1 - 2008
N2 - We study a natural probabilistic model for motif discovery that has been used to experimentally test the quality of motif discovery programs. In this model, there are k background sequences, and each character in a background sequence is a random character from an alphabet ∑. A motif G=g 1 g 2...g m is a string of m characters. Each background sequence is implanted a randomly generated approximate copy of G. For a randomly generated approximate copy b 1 b 2...b m of G, every character is randomly generated such that the probability for b i ≠g i is at most α. In this paper, we give the first analytical proof that multiple background sequences do help for finding subtle and faint motifs.
AB - We study a natural probabilistic model for motif discovery that has been used to experimentally test the quality of motif discovery programs. In this model, there are k background sequences, and each character in a background sequence is a random character from an alphabet ∑. A motif G=g 1 g 2...g m is a string of m characters. Each background sequence is implanted a randomly generated approximate copy of G. For a randomly generated approximate copy b 1 b 2...b m of G, every character is randomly generated such that the probability for b i ≠g i is at most α. In this paper, we give the first analytical proof that multiple background sequences do help for finding subtle and faint motifs.
UR - http://www.scopus.com/inward/record.url?scp=70349303350&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=70349303350&partnerID=8YFLogxK
U2 - 10.1007/978-3-540-79228-4_21
DO - 10.1007/978-3-540-79228-4_21
M3 - Conference contribution
AN - SCOPUS:70349303350
SN - 3540792279
SN - 9783540792277
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 234
EP - 245
BT - Theory and Applications of Models of Computation - 5th International Conference, TAMC 2008, Proceedings
PB - Springer Verlag
T2 - 5th International Conference on Theory and Applications of Models of Computation, TAMC 2008
Y2 - 25 April 2008 through 29 April 2008
ER -