Author(s): S.M. Vidanagamachchi | S.D. Dewasurendra | R.G. Ragel
Journal: International Journal of Research In Computer Science
ISSN 2249-8257
Volume: 2;
Issue: 6;
Start page: 33;
Date: 2012;
VIEW PDF
DOWNLOAD PDF 
Original page
Keywords: aho-corasick | commentz-walter | peptide identification
ABSTRACT
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.
Journal: International Journal of Research In Computer Science
ISSN 2249-8257
Volume: 2;
Issue: 6;
Start page: 33;
Date: 2012;
VIEW PDF
DOWNLOAD PDF Original pageKeywords: aho-corasick | commentz-walter | peptide identification
ABSTRACT
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.
