Efficient discovery of unique signatures on whole-genome EST databases

ABSTRACT

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.

REFERENCES

• 1: Sergey Brin , Rajeev Motwani , Jeffrey D. Ullman , Shalom Tsur, Dynamic itemset counting and implication rules for market basket data, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.255-264, May 11-15, 1997, Tucson, Arizona, United States
• 2: J. Burke, H. Wang, W. Hide, and D. B. Davison. Alternative gene form discovery and candidate gene selection from gene indexing projects. Genome Res., 8:276--290, 1998.
• 3: D. Gautheret, O. Poirot, F. Lopez, S. Audic, and J. M. Claverie. Alternate polyadenylation in human mRNAs: A large-scale analysis by EST clustering. Genome Res., 8:524--530, 1998.
• 4: C. Han, B. Sutherland, P. Jewett, M. Campbell, L. Meincke, J. Tesmer, M. Iundt, J. Fawcett, U. Kim, L. Deaven, and N. Doggett. Construction of a BAC contig map of chromosome 16q by two-dimensional overgo hybridization. Genome Res., 10(5):714--721, 2000.
• 5: H. P. Lee, Y. T. Tsai, C. H. Shih, T. F. Sheu, and C. Y. Tang. A Novel Approach for Efficient Query of Single Nucleotide Variation in DNA Databases. In Proc. of the Eighth Annual International Conference on Research in Computational Molecular Biology (RECOMB 2004), 2004.
• 6: F. Li and G. D. Stormo. Selection of optimal DNA oligos for gene expression arrays. Bioinformatics, 17:1067--1076, 2001.
• 7: L. Picoult-Newberg, T. E. Ideker, M. G. Pohl, S. L. Taylor, M. A. Donaldson, D. A. Nickerson, and M. Boyce-Jacino. Mining SNPs from EST databases. Genome Res., 9:167--174, 1999.
• 8: Sven Rahmann, Rapid Large-Scale Oligonucleotide Selection for Microarrays, Proceedings of the IEEE Computer Society Conference on Bioinformatics, p.54, August 14-16, 2002
• 9: J. M. Rouillard, C. J. Herbert, and M. Zuker. Oligoarray: Genome-scale oligonucleotide design for microarrays. Bioinformatics, 18(3):486--487, 2002.
• 10: A. O. Schmitt, T. Specht, G. Beckmann, E. Dahl, C. P. Pilarsky, B. Hinzmann, and A. Rosenthal. Exhaustive mining of EST libraries for genes differentially expressed in normal and tumour tissues. Nucleic Acids Res., 27:4251--4260, 1999.
• 11: K. Tanabe, S. Nakagomi, S. Kiryu-Seo, K. Kiryu, Y. Kiryu, T. Kiryu, M. Kiryu, and H. Kiyama. Expressed-sequence-tag approach to identify differentially expressed genes following peripheral nerve axotomy. Brain Res. Mol. Brain Res., 64:34--40, 1999.
• 12: Jie Zheng , Timothy J. Close , Tao Jiang , Stefano Lonardi, Efficient selection of unique and popular oligos for large EST databases†A preliminary version of this work was presented at the Symposium on Combinatorial Pattern Matching, Morelia, Mexico, and included in its Proceedings, pp. 273--283, LNCS 2676, Springer (2003)., Bioinformatics, v.20 n.13, p.2101-2112, September 2004 [doi>10.1093/bioinformatics/bth210]

INDEX TERMS

Primary Classification:
  J. Computer Applications
  J.3 LIFE AND MEDICAL SCIENCES

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval

General Terms:
Algorithms

Keywords:
mutant graph, pattern match, unique signature discovery, whole-genome EST database