Efficient algorithms for model-based motif discovery from multiple sequences

Bin Fu; Ming-Yang Kao; Lusheng Wang

doi:10.1007/978-3-540-79228-4_21

Efficient algorithms for model-based motif discovery from multiple sequences

Bin Fu^*, Ming-Yang Kao, Lusheng Wang

^*Corresponding author for this work

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

1 Scopus citations

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 ₁ g ₂...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 ₁ b ₂...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
Publisher	Springer Verlag
Pages	234-245
Number of pages	12
ISBN (Print)	3540792279, 9783540792277
DOIs	https://doi.org/10.1007/978-3-540-79228-4_21
State	Published - 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

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/978-3-540-79228-4_21

Fingerprint Dive into the research topics of 'Efficient algorithms for model-based motif discovery from multiple sequences'. Together they form a unique fingerprint.

Cite this

Fu, B., Kao, M-Y., & Wang, L. (2008). Efficient algorithms for model-based motif discovery from multiple sequences. In Theory and Applications of Models of Computation - 5th International Conference, TAMC 2008, Proceedings (pp. 234-245). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4978 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-540-79228-4_21

Fu, Bin ; Kao, Ming-Yang ; Wang, Lusheng. / Efficient algorithms for model-based motif discovery from multiple sequences. Theory and Applications of Models of Computation - 5th International Conference, TAMC 2008, Proceedings. Springer Verlag, 2008. pp. 234-245 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{491cc1648f354fa79c3d55a923cd5b87,

title = "Efficient algorithms for model-based motif discovery from multiple sequences",

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.",

author = "Bin Fu and Ming-Yang Kao and Lusheng Wang",

note = "Copyright: Copyright 2021 Elsevier B.V., All rights reserved.; 5th International Conference on Theory and Applications of Models of Computation, TAMC 2008 ; Conference date: 25-04-2008 Through 29-04-2008",

year = "2008",

doi = "10.1007/978-3-540-79228-4_21",

language = "English (US)",

isbn = "3540792279",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "234--245",

booktitle = "Theory and Applications of Models of Computation - 5th International Conference, TAMC 2008, Proceedings",

}

Fu, B, Kao, M-Y & Wang, L 2008, Efficient algorithms for model-based motif discovery from multiple sequences. in Theory and Applications of Models of Computation - 5th International Conference, TAMC 2008, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 4978 LNCS, Springer Verlag, pp. 234-245, 5th International Conference on Theory and Applications of Models of Computation, TAMC 2008, Xian, China, 4/25/08. https://doi.org/10.1007/978-3-540-79228-4_21

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. Springer Verlag, 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

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 -

Fu B, Kao M-Y, Wang L. Efficient algorithms for model-based motif discovery from multiple sequences. In Theory and Applications of Models of Computation - 5th International Conference, TAMC 2008, Proceedings. Springer Verlag. 2008. p. 234-245. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-540-79228-4_21