Skip Navigation

This Article
Right arrow Full Text Freely available
Right arrow Print PDF (478K) Freely available
Right arrow Supplementary Material
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Similar articles in ISI Web of Science
Right arrow Similar articles in PubMed
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrow Search for citing articles in:
ISI Web of Science (37)
Right arrow Commercial Re-use Guidelines
for Open Access NAR Content
Google Scholar
Right arrow Articles by Frith, M. C.
Right arrow Articles by Weng, Z.
Right arrow Search for Related Content
PubMed
Right arrow PubMed Citation
Right arrow Articles by Frith, M. C.
Right arrow Articles by Weng, Z.
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

Published online 2 January 2004

Nucleic Acids Research, 2004, Vol. 32, No. 1 189-200
© 2004 Oxford University Press

Finding functional sequence elements by multiple local alignment

Martin C. Frith1, Ulla Hansen1,2, John L. Spouge3 and Zhiping Weng*,1,4

1 Bioinformatics Program and 4 Department of Biomedical Engineering, Boston University, 44 Cummington Street, Boston, MA 02215, USA, 2 Department of Biology, Boston University, 5 Cummington Street, Boston, MA 02215, USA and 3 National Center for Biotechnology Information, National Library of Medicine, Building 38A, Bethesda, MD 20894, USA

*To whom correspondence should be addressed. Tel: +1 617 353 3509; Fax: +1 617 353 6766; Email: zhiping{at}bu.edu
Correspondence may also be addressed to John L. Spouge. Tel: +1 301 402 9310; Fax: +1 301 480 2288; Email: spouge{at}ncbi.nlm.nih.gov

Algorithms that detect and align locally similar regions of biological sequences have the potential to discover a wide variety of functional motifs. Two theoretical contributions to this classic but unsolved problem are presented here: a method to determine the width of the aligned motif automatically; and a technique for calculating the statistical significance of alignments, i.e. an assessment of whether the alignments are stronger than those that would be expected to occur by chance among random, unrelated sequences. Upon exploring variants of the standard Gibbs sampling technique to optimize the alignment, we discovered that simulated annealing approaches perform more efficiently. Finally, we conduct failure tests by applying the algorithm to increasingly difficult test cases, and analyze the manner of and reasons for eventual failure. Detection of transcription factor-binding motifs is limited by the motifs’ intrinsic subtlety rather than by inadequacy of the alignment optimization procedure.


Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?


This article has been cited by other articles:


Home page
 BioinformaticsHome page
J. S. Papadopoulos and R. Agarwala
COBALT: constraint-based alignment tool for multiple protein sequences
Bioinformatics, May 1, 2007; 23(9): 1073 - 1079.
[Abstract] [Full Text] [PDF]

Home page
 Nucleic Acids ResHome page
T. E. Reddy, B. E. Shakhnovich, D. S. Roberts, S. J. Russek, and C. DeLisi
Positional clustering improves computational binding site detection and identifies novel cis-regulatory sites in mammalian GABAA receptor subunit genes
Nucleic Acids Res., February 16, 2007; 35(3): e20 - e20.
[Abstract] [Full Text] [PDF]

Home page
 BioinformaticsHome page
N.-K. Kim, K. Tharakaraman, and J. L. Spouge
Adding sequence context to a Markov background model improves the identification of regulatory elements
Bioinformatics, December 1, 2006; 22(23): 2870 - 2875.
[Abstract] [Full Text] [PDF]

Home page
 Protein Eng Des SelHome page
T. Liu and R. Samudrala
The effect of experimental resolution on the performance of knowledge-based discriminatory functions for protein structure selection
Protein Eng. Des. Sel., September 1, 2006; 19(9): 431 - 437.
[Abstract] [Full Text] [PDF]

Home page
 Nucleic Acids ResHome page
C.-C. Liu, C.-C. Lin, W.-S. E. Chen, H.-Y. Chen, P.-C. Chang, J. J.W. Chen, and P.-C. Yang
CRSD: a comprehensive web server for composite regulatory signature discovery.
Nucleic Acids Res., July 1, 2006; 34(Web Server issue): W571 - W577.
[Abstract] [Full Text] [PDF]

Home page
 BioinformaticsHome page
Z. Wei and S. T. Jensen
GAME: detecting cis-regulatory elements using a genetic algorithm
Bioinformatics, July 1, 2006; 22(13): 1577 - 1584.
[Abstract] [Full Text] [PDF]

Home page
 BioinformaticsHome page
S. W. Ginzinger and J. Fischer
SimShift: Identifying structural similarities from NMR chemical shifts
Bioinformatics, February 15, 2006; 22(4): 460 - 465.
[Abstract] [Full Text] [PDF]

Home page
 BioinformaticsHome page
Q.-w. Dong, X.-l. Wang, and L. Lin
Application of latent semantic analysis to protein remote homology detection
Bioinformatics, February 1, 2006; 22(3): 285 - 290.
[Abstract] [Full Text] [PDF]

Home page
 BioinformaticsHome page
T.-J. Wu, Y.-H. Huang, and L.-A. Li
Optimal word sizes for dissimilarity measures and estimation of the degree of dissimilarity between DNA sequences
Bioinformatics, November 15, 2005; 21(22): 4125 - 4132.
[Abstract] [Full Text] [PDF]

Home page
 BioinformaticsHome page
G. E. Crooks, R. E. Green, and S. E. Brenner
Pairwise alignment incorporating dipeptide covariation
Bioinformatics, October 1, 2005; 21(19): 3704 - 3710.
[Abstract] [Full Text] [PDF]

Home page
 Physiol. GenomicsHome page
L. Yu, P. M. Haverty, J. Mariani, Y. Wang, H.-Y. Shen, M. A. Schwarzschild, Z. Weng, and J.-F. Chen
Genetic and pharmacological inactivation of adenosine A2A receptor reveals an Egr-2-mediated transcriptional regulatory network in the mouse striatum
Physiol Genomics, September 21, 2005; 23(1): 89 - 102.
[Abstract] [Full Text] [PDF]

Home page
 Nucleic Acids ResHome page
C. Bi and P. K. Rogan
Bipartite pattern discovery by entropy minimization-based multiple local alignment
Nucleic Acids Res., September 23, 2004; 32(17): 4979 - 4991.
[Abstract] [Full Text] [PDF]

Home page
 Nucleic Acids ResHome page
M. C. Frith, Y. Fu, L. Yu, J.-F. Chen, U. Hansen, and Z. Weng
Detection of functional DNA motifs via statistical over-representation
Nucleic Acids Res., February 26, 2004; 32(4): 1372 - 1381.
[Abstract] [Full Text] [PDF]

Home page
 Nucleic Acids ResHome page
P. M. Haverty, U. Hansen, and Z. Weng
Computational inference of transcriptional regulatory networks from expression profiling and transcription factor binding site identification
Nucleic Acids Res., January 2, 2004; 32(1): 179 - 188.
[Abstract] [Full Text] [PDF]


Disclaimer:
Please note that abstracts for content published before 1996 were created through digital scanning and may therefore not exactly replicate the text of the original print issues. All efforts have been made to ensure accuracy, but the Publisher will not be held responsible for any remaining inaccuracies. If you require any further clarification, please contact our Customer Services Department.