Vol. 20 no. 1 2004, pages 29-39
Bioinformatics © Oxford University Press 2004; all rights reserved.
Efficient filtering methods for clustering cDNAs with spliced sequence alignment
1 IBM Tokyo Research Laboratory, 1623-14, Shimo-tsuruma, Yamato, Kanagawa 242-8502, Japan and 2 RIKEN Genomic Sciences Center, Bioinformatics Group, 1-7-22, Suehiro-cho, Tsurumi, Yokohama, Kanagawa 230-0045, Japan
Received on April 2, 2003
; revised on June 26, 2003
; accepted on July 3, 2003
Motivation: Clustering sequences of a full-length cDNA library into alternative splice form candidates is a very important problem.
Results: We developed a new efficient algorithm to cluster sequences of a full-length cDNA library into alternative splice form candidates. Current clustering algorithms for cDNAs tend to produce too many clusters containing incorrect splice form candidates. Our algorithm is based on a spliced sequence alignment algorithm that considers splice sites. The spliced sequence alignment algorithm is a variant of an ordinary dynamic programming algorithm, which requires O(nm) time for checking a pair of sequences where n and m are the lengths of the two sequences. Since the time bound is too large to perform all-pair comparison for a large set of sequences, we developed new techniques to reduce the computation time without affecting the accuracy of the output clusters. Our algorithm was applied to 21 076 mouse cDNA sequences of the FANTOM 1.10 database to examine its performance and accuracy. In these experiments, we achieved about 2–12-fold speedup against a method using only a traditional hash-based technique. Moreover, without using any information of the mouse genome sequence data or any gene data in public databases, we succeeded in listing 87–89% of all the clusters that biologists have annotated manually.
Availability: We provide a web service for cDNA clustering located at https://access.obigrid.org/ibm/cluspa/, for which registration for the OBIGrid (http://www.obigrid.org) is required.
Contact: tshibuya{at}jp.ibm.com
* To whom correspondence should be addressed.
CiteULike 
Connotea 
Del.icio.us What's this?
This article has been cited by other articles:
|
|
 |
|
  A. Masoudi-Nejad, K. Tonomura, S. Kawashima, Y. Moriya, M. Suzuki, M. Itoh, M. Kanehisa, T. Endo, and S. Goto EGassembler: online bioinformatics service for large-scale processing, clustering and assembling ESTs and genomic DNA fragments. Nucleic Acids Res., July 1, 2006; 34(Web Server issue): W459 - W462. [Abstract] [Full Text] [PDF]
|
|