Rapid and sensitive dot-matrix methods for genome analysis.pdf

1Rapid and Sensitive Dot-matrix Methods for Genome Analysis Authors: Yue Huang* and Ling Zhang Address: Lynnon Corporation, 116 rue du Milicien, Vaudreuil-Dorion, Quebec, Canada, J7V 9M4 Phone: 1-450-455-4894 Fax: 1-450-455-4269 *To whom correspondence should be addressed Bioinformatics Advance Access published February 5, 2004 Copyright (c) 2004 Oxford University Press 2Abstract 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 hundred kilobases, analysis of genome sequences with a length of 10 megabases 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 megabases) with both strands was generated in 80 seconds with a 1GHz personal computer. Availability: The implementation of the described methods in C language is available at /dotplot/index.html. Contact: yhuang@ Running title: Dot-matrix methods for genome analysis Keywords: Genome analysis; dot-matrix; algorithm; fast search; DNA; sequence analysis 3Introduction Dot-matrix analysis is an efficient method to search for similarities between two sequences (Gibbs and McIntyre 1970, Argos 1987, Risler et a