Bioinformatics Advance Access originally published online on January 22, 2004
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Bioinformatics 20(4) © Oxford University Press 2004; all rights reserved.
Rapid and sensitive dot-matrix methods for genome analysis
Lynnon Corporation, 116 rue du Milicien, Vaudreuil-Dorion, Quebec, Canada, J7V 9M4
Received on November 6, 2002
; revised on April 23, 2003
; accepted on July 22, 2003
Advance Access Publication January 22, 2004
Motivation: Dot-matrix plots are widely used for similarity analysis of biological sequences. Many algorithms and computer software tools have been developed for this purpose. Though some of these tools have been reported to handle sequences of a few 100 kb, analysis of genome sequences with a length of >10 Mb on a microcomputer is still impractical due to long execution time and computer memory requirement.
Results: Two dot-matrix comparison methods have been developed for analysis of large sequences. The methods initially locate similarity regions between two sequences using a fast word search algorithm, followed with an explicit comparison on these regions. Since the initial screening removes most of random matches, the computing time is substantially reduced. The methods produce high quality dot-matrix plots with low background noise. Space requirements are linear, so the algorithms can be used for comparison of genome size sequences. Computing speed may be affected by highly repetitive sequence structures of eukaryote genomes. A dot-matrix plot of Yeast genome (12 Mb) with both strands was generated in 80 s with a 1 GHz personal computer.
Availability: The implementation of the described methods in C language is available at http://www.lynnon.com/dotplot/index.html
Contact: yhuang{at}lynnon.com
* To whom correspondence should be addressed.
CiteULike 
Connotea 
Del.icio.us What's this?
This article has been cited by other articles:
|
|
 |
|
  J. Krumsiek, R. Arnold, and T. Rattei Gepard: a rapid and sensitive tool for creating dotplots on genome scale Bioinformatics, April 15, 2007; 23(8): 1026 - 1028. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 C. Putonti, Y. Luo, C. Katili, S. Chumakov, G. E. Fox, D. Graur, and Y. Fofanov A Computational Tool for the Genomic Identification of Regions of Unusual Compositional Properties and Its Utilization in the Detection of Horizontally Transferred Sequences Mol. Biol. Evol., October 1, 2006; 23(10): 1863 - 1868. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
H. Yang and A. R. Gingle OxfordGrid: a web interface for pairwise comparative map views Bioinformatics, December 1, 2005; 21(23): 4307 - 4308. [Abstract] [Full Text] [PDF]
|
|