cWINNOWER algorithm for finding fuzzy dna motifs

Liang, S.; Samanta, M. P.; Biegel, B. A.

Home/Archive/NASA NTRS

NASA NTRS · 20050151752

cWINNOWER algorithm for finding fuzzy dna motifs

Liang, S.·Samanta, M. P.·Biegel, B. A.

View original source ↗Export metadata ↓

Abstract

The cWINNOWER algorithm detects fuzzy motifs in DNA sequences rich in protein-binding signals. A signal is defined as any short nucleotide pattern having up to d mutations differing from a motif of length l. The algorithm finds such motifs if a clique consisting of a sufficiently large number of mutated copies of the motif (i.e., the signals) is present in the DNA sequence. The cWINNOWER algorithm substantially improves the sensitivity of the winnower method of Pevzner and Sze by imposing a consensus constraint, enabling it to detect much weaker signals. We studied the minimum detectable clique size qc as a function of sequence length N for random sequences. We found that qc increases linearly with N for a fast version of the algorithm based on counting three-member sub-cliques. Imposing consensus constraints reduces qc by a factor of three in this case, which makes the algorithm dramatically more sensitive. Our most sensitive algorithm, which counts four-member sub-cliques, needs a minimum of only 13 signals to detect motifs in a sequence of length N = 12,000 for (l, d) = (15, 4). Copyright Imperial College Press.

Explore related subjects

Evaluation Studies Validation Studies Gene Expression Profiling/methods Amino Acid Motifs/genetics Sequence Alignment/methods Algorithms DNA/chemistry/genetics Sequence Analysis, DNA/methods Protein Binding/genetics Fuzzy Logic Binding Sites/genetics Base Sequence Sensitivity and Specificity Sequence Homology, Nucleic Acid Reproducibility of Results Stochastic Processes Molecular Sequence Data Comparative Study

Keep this discovery

Explore connections, maps & timelines

BibTeX RIS

Liang, S., Samanta, M. P., Biegel, B. A.. 2004-03-01. cWINNOWER algorithm for finding fuzzy dna motifs. https://ntrs.nasa.gov/citations/20050151752

Cite the original work for its findings. Save a collection to share your selection of sources.

KEEP EXPLORING

Related reports

NASA NTRS2005

Elastic model for crimped collagen fibrils

A physiologic constitutive expression is presented in algorithmic format for the nonlinear elastic response of wavy collagen fibrils found in soft connective tissues. The model is based on the observation that crimped fibrils in a fascicle have a three-dimensional structure at the micron scale that we approximate as a helical spring. The symmetry of this wave form allows the force/displacement relationship derived from Castigliano's theorem to be solved in closed form: all integrals become analytic. Model predictions are in good agreement with experimental observations for mitral-valve chordae tendinece.

Evaluation Studies↗

NASA NTRS2005

Length dependence of carbon nanotube thermal conductivity and the "problem of long waves"

We present the first calculations of finite length carbon nanotube thermal conductivity that extend from the ballistic to the diffusive regime, throughout a very wide range of lengths and temperatures. The long standing problem of vanishing scattering of the "long wavelength phonf dramatically here, making the thermal conductivity diverge as the nanotube length increases. We show that the divergence disappears if 3-phonon scattering processes are considered to second or higher order. Nevertheless, for defect free nanotubes, the thermal conductivity keeps increasing up to very large lengths (10 gm at 300 K). Defects in the nanotube are also able to remove the long wavelength divergence.

Evaluation Studies↗

NASA NTRS2005

Use of multiresolution wavelet feature pyramids for automatic registration of multisensor imagery

The problem of image registration, or the alignment of two or more images representing the same scene or object, has to be addressed in various disciplines that employ digital imaging. In the area of remote sensing, just like in medical imaging or computer vision, it is necessary to design robust, fast, and widely applicable algorithms that would allow automatic registration of images generated by various imaging platforms at the same or different times and that would provide subpixel accuracy. One of the main issues that needs to be addressed when developing a registration algorithm is what type of information should be extracted from the images being registered, to be used in the search for the geometric transformation that best aligns them. The main objective of this paper is to evaluate several wavelet pyramids that may be used both for invariant feature extraction and for representing images at multiple spatial resolutions to accelerate registration. We find that the bandpass wavelets obtained from the steerable pyramid due to Simoncelli performs best in terms of accuracy and consistency, while the low-pass wavelets obtained from the same pyramid give the best results in terms of the radius of convergence. Based on these findings, we propose a modification of a gradient-based registration algorithm that has recently been developed for medical data. We test the modified algorithm on several sets of real and synthetic satellite imagery.

Evaluation Studies↗