High similarity sequence comparison in clustering large sequence databases.
We present a fast algorithm for sequence clustering and searching which works with large sequence databases. It uses a strictly defined similarity measure. The algorithm is faster than conventional EST clustering approaches because its complexity is directly related to the number of subwords shared by the sequences. Furthermore, the algorithm also works with proteic sequences and large sequences like entire chromosomes. We present a theoretical study of our approach and provide experimental results.
Dudoignon
Lorie
L
IMT, INRIA, Marseille Cedex 20, 13451, France. Lorie.Dudoignon@sophia.inria.fr
Glemet
Eric
E
Heus
Hendrik Cornelis
HC
Raffinot
Mathieu
M
D000465:Algorithms; D002874:Chromosome Mapping / Q000379:methods*; D016000:Cluster Analysis; D003628:Database Management Systems; D030541:Databases, Genetic; D016247:Information Storage and Retrieval / Q000379:methods; D010363:Pattern Recognition, Automated / Q000379:methods*; D016415:Sequence Alignment / Q000379:methods*; D017421:Sequence Analysis / Q000379:methods*