Abstract
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.
| Original language | English (US) |
|---|---|
| Title of host publication | Theory and Applications of Models of Computation - 5th International Conference, TAMC 2008, Proceedings |
| Pages | 234-245 |
| Number of pages | 12 |
| DOIs | |
| State | Published - Dec 1 2008 |
| Event | 5th International Conference on Theory and Applications of Models of Computation, TAMC 2008 - Xian, China Duration: Apr 25 2008 → Apr 29 2008 |
Publication series
| Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
|---|---|
| Volume | 4978 LNCS |
| ISSN (Print) | 0302-9743 |
| ISSN (Electronic) | 1611-3349 |
Other
| Other | 5th International Conference on Theory and Applications of Models of Computation, TAMC 2008 |
|---|---|
| Country | China |
| City | Xian |
| Period | 4/25/08 → 4/29/08 |
Fingerprint
ASJC Scopus subject areas
- Theoretical Computer Science
- Computer Science(all)
Cite this
}
Efficient algorithms for model-based motif discovery from multiple sequences. / Fu, Bin; Kao, Ming-Yang; Wang, Lusheng.
Theory and Applications of Models of Computation - 5th International Conference, TAMC 2008, Proceedings. 2008. p. 234-245 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4978 LNCS).Research output: Chapter in Book/Report/Conference proceeding › Conference contribution
TY - GEN
T1 - Efficient algorithms for model-based motif discovery from multiple sequences
AU - Fu, Bin
AU - Kao, Ming-Yang
AU - Wang, Lusheng
PY - 2008/12/1
Y1 - 2008/12/1
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
ER -