Genome comparison without alignment using shortest unique substrings.

ABSTRACT:

Background

Sequence comparison by alignment is a fundamental tool of molecular biology. In this paper we show how a number of sequence comparison tasks, including the detection of unique genomic regions, can be accomplished efficiently without an alignment step. Our procedure for nucleotide sequence comparison is based on shortest unique substrings. These are substrings which occur only once within the sequence or set of sequences analysed and which cannot be further reduced in length without losing the property of uniqueness. Such substrings can be detected using generalized suffix trees.

Results

We find that the shortest unique substrings in Caenorhabditis elegans, human and mouse are no longer than 11 bp in the autosomes of these organisms. In mouse and human these unique

SUBMITTER: Haubold B 

PROVIDER: S-EPMC1166540 | biostudies-literature | 2005 May

REPOSITORIES: biostudies-literature