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

Department of Computer Science

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

1 Citation (Scopus)

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. © 2008 Springer-Verlag Berlin Heidelberg.

Original language	English
Title of host publication	Theory and Applications of Models of Computation
Subtitle of host publication	5th International Conference, TAMC 2008, Proceedings
Publisher	Springer Verlag
Pages	234-245
Volume	4978 LNCS
ISBN (Print)	3540792279, 9783540792277
DOIs	https://doi.org/10.1007/978-3-540-79228-4_21
Publication status	Published - 2008
Event	5th International Conference on Theory and Applications of Models of Computation, TAMC 2008 - Xian, China Duration: 25 Apr 2008 → 29 Apr 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

Conference

Conference	5th International Conference on Theory and Applications of Models of Computation, TAMC 2008
Country/Territory	China
City	Xian
Period	25/04/08 → 29/04/08

Access Output

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

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

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 (Vol. 4978 LNCS, 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. Vol. 4978 LNCS Springer Verlag, 2008. pp. 234-245 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{266db644f651449cb4be20e305bb092c,

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. {\textcopyright} 2008 Springer-Verlag Berlin Heidelberg.",

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

year = "2008",

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

language = "English",

isbn = "3540792279",

volume = "4978 LNCS",

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

address = "Germany",

note = "5th International Conference on Theory and Applications of Models of Computation, TAMC 2008 ; Conference date: 25-04-2008 Through 29-04-2008",

}

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. vol. 4978 LNCS, 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, 25/04/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. Vol. 4978 LNCS 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: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

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. © 2008 Springer-Verlag Berlin Heidelberg.

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. © 2008 Springer-Verlag Berlin Heidelberg.

UR - http://www.scopus.com/inward/record.url?scp=70349303350&partnerID=8YFLogxK

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-70349303350&origin=recordpage

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

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

M3 - RGC 32 - Refereed conference paper (with host publication)

SN - 3540792279

SN - 9783540792277

VL - 4978 LNCS

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

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 MY, 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. Vol. 4978 LNCS. Springer Verlag. 2008. p. 234-245. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-540-79228-4_21

Efficient algorithms for model-based motif discovery from multiple sequences

Abstract

Publication series

Conference

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this