Sublinear time motif discovery from multiple sequences

DOI10.3390/A6040636MaRDI QIDQ1736589zbMATH OpenOpenAlexFDO

Authors Bin Fu, Yunhui Fu, Yuan Xue

Publication date 26 March 2019

Published in Algorithms (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1007.2618

zbMATH Keywords

randomized algorithmdeterministic algorithmmotif discoverysublinear time

Mathematics Subject Classification ID

Protein sequences, DNA sequences (92D20) Randomized algorithms (68W20) Computational methods for problems pertaining to biology (92-08) Algorithms on strings (68W32)

Abstract: A natural probabilistic model for motif discovery 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 $Sigma$. A motif $G=g_1{g}_2\mathrm{...}{g}_m$ is a string of $m$ characters. Each background sequence is implanted a probabilistically generated approximate copy of $G$. For a probabilistically generated approximate copy $b_1{b}_2\mathrm{...}{b}_m$ of $G$, every character $b_i$ is probabilistically generated such that the probability for $b_{i}eq{g}_i$ is at most $alpha$. We develop three algorithms that under the probabilistic model can find the implanted motif with high probability via a tradeoff between computational time and the probability of mutation. The methods developed in this paper have been used in the software implementation. We observed some encouraging results that show improved performance for motif detection compared with other softwares.

Recommendations

• Discovering Almost Any Hidden Motif from Multiple Sequences in Polynomial Time with Low Sample Complexity and High Success Probability
• Efficient Algorithms for Model-Based Motif Discovery from Multiple Sequences
• Discovering almost any hidden motif from multiple sequences
• Probabilistic analysis of a motif discovery algorithm for multiple sequences
• Algorithms and Computation

Cites work

• scientific article; zbMATH DE number 3567782 (Why is no real title available?)
• scientific article; zbMATH DE number 1305511 (Why is no real title available?)
• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• Algorithms on Strings, Trees and Sequences
• Discovering almost any hidden motif from multiple sequences
• Distinguishing string selection problems.
• Finding similar regions in many strings
• On covering problems of codes
• On the closest string and substring problems
• Probabilistic analysis of a motif discovery algorithm for multiple sequences

Cited in

(14)

• Probabilistic analysis of a motif discovery algorithm for multiple sequences
• Discovering almost any hidden motif from multiple sequences
• Analysis method and algorithm design of biological sequence problem based on generalized k-mer vector
• Efficient Algorithms for Model-Based Motif Discovery from Multiple Sequences
• Discovering Almost Any Hidden Motif from Multiple Sequences in Polynomial Time with Low Sample Complexity and High Success Probability
• Toward optimal motif enumeration.
• String Processing and Information Retrieval
• Identification of Distinguishing Motifs
• Space and Time Efficient Algorithms for Planted Motif Search
• Editorial: Special issue on algorithms for sequence analysis and storage
• New Bounds for Motif Finding in Strong Instances
• Algorithms and Computation
• Combinatorial Pattern Matching
• An upper bound on the hardness of exact matrix based motif discovery

Describes a project that uses

Uses Software

• WebMOTIFS
• PhyME

This page was built for publication: Sublinear time motif discovery from multiple sequences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1736589)