Efficient algorithms for model-based motif discovery from multiple sequences

Bin Fu*, Ming-Yang Kao, Lusheng Wang

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference 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 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 languageEnglish (US)
Title of host publicationTheory and Applications of Models of Computation - 5th International Conference, TAMC 2008, Proceedings
Pages234-245
Number of pages12
DOIs
StatePublished - Dec 1 2008
Event5th International Conference on Theory and Applications of Models of Computation, TAMC 2008 - Xian, China
Duration: Apr 25 2008Apr 29 2008

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4978 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other5th International Conference on Theory and Applications of Models of Computation, TAMC 2008
CountryChina
CityXian
Period4/25/084/29/08

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

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). https://doi.org/10.1007/978-3-540-79228-4-21