Finding Motifs Using Random Projections

By Jeremy D. Buhler, Martin Tompa. Annual International Conference on Research in Computational Molecular Biology, 2001

686 citations recorded by the source corpus.

View Paper: https://www.semanticscholar.org/paper/68d3576897a7314886dad66338e43b40371f2763

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Molecular Biology

Citations in the corpus

Combining phylogenetic data with co-regulated genes to identify regulatory motifs (2003, background): “…and Hartzell, 1989; Hertz and Stormo, 1999), MEME (Bailey and Elkan, 1994, 1995), ANN-Spec (Workman and Stormo, 2000), AlignACE (Hughes et al ., 2000), Projection (Buhler and Tompa, 2002), MITRA (Eskin and Pevzner, 2002), and FootPrinter (Blanchette and Tompa, 2002; Blanchette et al ., 2002).”
An algorithm for finding signals of unknown length in DNA sequences (2001, methodology): “…widely used algorithms the pattern driven approach has been abandoned, and the signal is extracted by analyzing and comparing the patterns that occur in the sequences (see for example (Lawrence et al., 1993; Bailey & Elkan, 1995; Hertz & Stormo, 1999; Pevzner & Sze, 2000; Buhler & Tompa, 2001)).”
Locality-sensitive hashing scheme based on p-stable distributions (2004, background): “This is due to the fact that, in many cases, approximate nearest neighbor is almost as good as the exact one; in particular, if the distance measure accurately captures the notion of user quality, then small differences in the distance should not matter.”
A survey of DNA motif finding algorithms (2007, background): “Gibbs sampling is one of the most promising pattern discovery methods in terms of its flexibility and wide range of application, however, it is known to be rather strongly affected by the local optima problem [49].”
Finding Motifs in Time Series (2002, methodology): “We call such patterns motifs, because of their close analogy to their discrete counterparts in computation biology [11, 16, 30, 34, 36].”
A symbolic representation of time series, with implications for streaming algorithms (2003, methodology): “In addition to use with streaming algorithms, there is an enormous wea lth of useful definitions, algorithms and data structures in the bioinformatics literature that can be exploited by our representat ion [3, 13, 17, 28, 29, 32, 33].”
Experiencing SAX: a novel symbolic representation of time series (2007, background): “…wealth of useful deﬁnitions, algorithms and data structures in the bioinformatics literature that can be exploited by our representation (Apostolico et al. 2002; Durbin et al. 1998; Gionis and Mannila 2003; Lonardi et al. 2001; Reinert et al. 2000; Staden et al. 1989; Tompa and Buhler 2001).”
Approximate Nearest Neighbor: Towards Removing the Curse of Dimensionality (2012, background): “Lower bounds for such embeddings have been investigated as well [KN05].”
Probabilistic discovery of time series motifs (2003, methodology): “MOTIF DISCOVERY AND THE RANDOM PROJECTION ALGORITHM The projection algorithm by Buhler and Tompa was designed to attack the planted (w,d)-motif problem, which was proposed by Pevzner and Sze [28].”
Finding composite regulatory patterns in DNA sequences (2002, methodology): “Although Buhler and Tompa (2001), and Keich and Pevzner (2002a) designed the algorithms to ﬁnd ( 14 , 4 ) motifs, a more difﬁcult problem of ﬁnding motifs that only occur in 13 out of 20 sequences in the sample (corrupted sample) is almost impossible to solve.”
Fast Shapelets: A Scalable Algorithm for Discovering Time Series Shapelets (2013, methodology): “right, if we mask conservatively, but do multiple random masks, we can make the probability of false dismissals arbitrarily low while not incurring a measurable increase in false positives [24].”
Very sparse random projections (2006, methodology): “INTRODUCTION Random projections [1, 43] have been used in Machine Learning [2,4,5,13,14,22], VLSI layout [42], analysis of Latent Semantic Indexing (LSI) [35], set intersections [7, 36], finding motifs in bio-sequences [6, 27], face recognition [16], privacy preserving distributed data mining [31], ”
SHRiMP: Accurate Mapping of Short Color-space Reads (2009, background): “An alternative approach generates a set of subsequences from the read (often represented as spaced seeds [7,10,12]), again in such a manner that if a read were to match at a particular location with some number of mismatches, at least one of the subsequences would match the genome [5,9].”
PatternHunter: faster and more sensitive homology search (2002, background): “See also Buhler and Tompa (2002)”
Efficient large-scale sequence comparison by locality-sensitive hashing (2001, methodology): “We have successfully applied this idea to improve the sensitivity of motif-finding algorithms (Buhler and Tompa, 2001).”