Clustered sequence representation for fast homology search. Export

@article{citeulike:2910998, abstract = {We present a novel approach to managing redundancy in sequence databanks such as GenBank. We store clusters of near-identical sequences as a representative union-sequence and a set of corresponding edits to that sequence. During search, the query is compared to only the union-sequences representing each cluster; cluster members are then only reconstructed and aligned if the union-sequence achieves a sufficiently high score. Using this approach with BLAST results in a 27\% reduction in collection size and a corresponding 22\% decrease in search time with no significant change in accuracy. We also describe our method for clustering that uses fingerprinting, an approach that has been successfully applied to collections of text and web documents in Information Retrieval. Our clustering approach is ten times faster on the GenBank nonredundant protein database than the fastest existing approach, CD-HIT. We have integrated our approach into FSA-BLAST, our new Open Source version of BLAST (available from http://www.fsa-blast.org/). As a result, FSA-BLAST is twice as fast as NCBI-BLAST with no significant change in accuracy.}, address = {School of Computer Science and Information Technology, RMIT University, Melbourne, Australia. mcam@cs.rmit.edu.au}, author = {Cameron, M. and Bernstein, Y. and Williams, H. E.}, citeulike-article-id = {2910998}, citeulike-linkout-0 = {http://dx.doi.org/10.1089/cmb.2007.R005}, citeulike-linkout-1 = {http://view.ncbi.nlm.nih.gov/pubmed/17683263}, citeulike-linkout-2 = {http://www.hubmed.org/display.cgi?uids=17683263}, doi = {10.1089/cmb.2007.R005}, issn = {1066-5277}, journal = {Journal of computational biology : a journal of computational molecular cell biology}, keywords = {algorithm, blast, clustering, open-source, software}, month = {June}, number = {5}, pages = {594--614}, posted-at = {2009-07-02 20:20:35}, priority = {2}, title = {Clustered sequence representation for fast homology search.}, url = {http://dx.doi.org/10.1089/cmb.2007.R005}, volume = {14}, year = {2007} }

TY - JOUR ID - citeulike:2910998 L3 - citeulike-article-id:2910998 N2 - We present a novel approach to managing redundancy in sequence databanks such as GenBank. We store clusters of near-identical sequences as a representative union-sequence and a set of corresponding edits to that sequence. During search, the query is compared to only the union-sequences representing each cluster; cluster members are then only reconstructed and aligned if the union-sequence achieves a sufficiently high score. Using this approach with BLAST results in a 27% reduction in collection size and a corresponding 22% decrease in search time with no significant change in accuracy. We also describe our method for clustering that uses fingerprinting, an approach that has been successfully applied to collections of text and web documents in Information Retrieval. Our clustering approach is ten times faster on the GenBank nonredundant protein database than the fastest existing approach, CD-HIT. We have integrated our approach into FSA-BLAST, our new Open Source version of BLAST (available from http://www.fsa-blast.org/). As a result, FSA-BLAST is twice as fast as NCBI-BLAST with no significant change in accuracy. IS - 5 JF - Journal of computational biology : a journal of computational molecular cell biology SN - 1066-5277 AD - School of Computer Science and Information Technology, RMIT University, Melbourne, Australia. mcam@cs.rmit.edu.au EP - 614 TI - Clustered sequence representation for fast homology search. VL - 14 SP - 594 KW - algorithm KW - blast KW - clustering KW - open-source KW - software AU - Cameron, M AU - Bernstein, Y AU - Williams, HE PY - 2007/06// UR - http://dx.doi.org/10.1089/cmb.2007.R005 ER -