Sequence Alignment as a Database Technology Challenge

Abstract. Sequence alignment is an important task for molecular biolo-gists. Because alignment basically deals with approximate string match-ing on large biological sequence collections, it is both data intensive and computationally complex. There exist several tools for the variety of problems related to sequence alignment. Our first observation is that the term ’sequence database ’ is used in general for textually formatted string collections. A second observation is that the search tools are specifically dedicated to a single problem. They have limited capabilities to serve as a solution for related problems that require minor adaptations. Our aim is to show the possibilities and advantages of a DBMS-based ap-proach toward sequence alignment. For this purpose, we will adopt tech-niques from single sequence alignment to speed up multiple sequence alignment. We will show how the problem of matching a protein string family against a large protein string database can be tackled with q-gram indexing techniques based on relational database technology. The use of Monet, a main-memory DBMS, allows us to realize a flexible en-vironment for developing searching heuristics that outperform classical dynamic programming, while keeping up satisfying sensitivity figures.