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

deterministic algorithmmotif discoveryrandomized algorithmsublinear time

Mathematics Subject Classification ID

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

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.

Review text

Summary: In this paper, 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 \dots g_m\) is a string of \(m\) characters. In each background sequence is implanted a probabilistically-generated approximate copy of \(G\). For a probabilistically-generated approximate copy \(b_1 b_2 \dots b_m\) of \(G\), every character, \(b_i\), is probabilistically generated, such that the probability for \(b_i \neq g_i\) is at most \(\alpha\). We develop two new randomized algorithms and one new deterministic algorithm. They make advancements in the following aspects: (1) The algorithms are much faster than those before. Our algorithms can even run in sublinear time. (2) They can handle any motif pattern. (3) The restriction for the alphabet size is a lower bound of four. This gives them potential applications in practical problems, since gene sequences have an alphabet size of four. (4) All algorithms have rigorous proofs about their performances. 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 software.

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

• Algorithms on Strings, Trees and Sequences
• Discovering almost any hidden motif from multiple sequences
• Distinguishing string selection problems.
• Finding similar regions in many strings
• 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?)
• 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)

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