Genetic and Protein Engineering

Biography

Biography: Abdellah Salhi

Abstract

Sequence analysis is at the core of bioinformatics. Many algorithms have been developed for the purpose, which, almost invariably, try to measure the similarity between sequences of symbols drawn from finite sets but with varied cardinalities. These algorithms are in two broad classes: deterministic and stochastic. Deterministic algorithms are often hard to implement and are slow in practice. Stochastic algorithms, on the other hand, are relatively easier to implement and are efficient. However, they do not guarantee to find the correct solution when it exists. This limits their use particularly where it is essential to know the exact solution as in medical situations. The inherent uncertainty in the outcomes of deterministic approaches is exacerbated by the need to arbitrarily set a number of parameters on which they depend. Default values of these parameters are often inappropriate outside the context in which they were estimated. There is, therefore, room for deterministic algorithms particularly when the time constraint is soft. In this paper we highlight the limitations of stochastics algorithms on probably the most prominent genomics search tool, namely the Basic Local Search Tool or BLAST. We then present an algorithm which, besides being deterministic, is easy to understand and implement. We illustrate it on Shotgun Proteomics Data and compare it with a number of other well-known sequence comparison algorithms such as the Needleman-Wunch and Smith-Waterman algorithms.