Efficient discovery of unique signatures on whole-genome EST databases

Expressed Sequence Tags (EST) are widely used for the discovery of new genes, particularly those involved in human disease processes. A subsequence in an EST dataset is unique if it appears only in one EST sequence of the dataset but does not appear in any other EST sequence. The unique subsequences can be regarded as signatures that distinguish an EST from all the others, and provide valuable information for many applications, such as PCR primer designs and microarray experiments. The discoveries of unique signatures on large-scale EST datasets are previously computational challenges. In this paper, we propose two efficient algorithms to extract the unique signatures from EST databases. The algorithms perform impressive discovery efficiencies in the experiments on real human ESTs.