Commentz-Walter: Any Better than Aho-Corasick for Peptide Identification?

An algorithm for locating all occurrences of a finite number of keywords in an arbitrary string, also known as multiple strings matching, is commonly required in information retrieval (such as sequence analysis, evolutionary biological studies, gene/protein identification and network intrusion detec...

Full description

Saved in:
Bibliographic Details
Published in:International journal of research in computer science 2012-11, Vol.2 (6), p.33-37
Main Authors: Vidanagamachchi, S.M., Dewasurendra, S.D., Ragel, R.G., Niranjan, M.
Format: Article
Language:English
Subjects:
Algorithms
Biological
Editing
Evolutionary
Networks
Peptides
String matching
Texts
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:An algorithm for locating all occurrences of a finite number of keywords in an arbitrary string, also known as multiple strings matching, is commonly required in information retrieval (such as sequence analysis, evolutionary biological studies, gene/protein identification and network intrusion detection) and text editing applications. Although Aho-Corasick was one of the commonly used exact multiple strings matching algorithm, Commentz-Walter has been introduced as a better alternative in the recent past. Comments-Walter algorithm combines ideas from both Aho-Corasick and Boyer Moore. Large scale rapid and accurate peptide identification is critical in computational proteomics. In this paper, we have critically analyzed the time complexity of Aho-Corasick and Commentz-Walter for their suitability in large scale peptide identification. According to the results we obtained for our dataset, we conclude that Aho-Corasick is performing better than Commentz-Walter as opposed to the common beliefs. [PUBLICATION ABSTRACT]
ISSN:2249-8257
2249-8265
DOI:10.7815/ijorcs.26.2012.053