Heuristic Pairwise Alignment in Database Environments

Abstract

Biological data have gained wider recognition during the last few years, although managing and processing these data in an efficient way remains a challenge in many areas. Increasingly, more DNA sequence databases can be accessed; however, most algorithms on these sequences are performed outside of the database with different bioinformatics software. In this article, we propose a novel approach for the comparative analysis of sequences, thereby defining heuristic pairwise alignment inside the database environment. This method takes advantage of the benefits provided by the database management system and presents a way to exploit similarities in data sets to quicken the alignment algorithm. We work with the column-oriented MonetDB, and we further discuss the key benefits of this database system in relation to our proposed heuristic approach.

Keywords: bioinformatics; database systems; pairwise alignment.

Figure 1

Flowchart of the GLASS steps.

Figure 2

Flowchart of our heuristic algorithm steps.

Figure 3

Example of inserting subalignments of length 4 into a sequence.

Figure 4

The tables used in the heuristic pairwise alignment.

Figure 5

Standard deviation (y axis) depending on the size of the sample set (x axis) and length of the k-mers in the case of fixed gap penalty: (a) k = 5; (b) k = 7; (c) k = 10; and (d) k = 15.

Figure 6

Standard deviation (y axis) depending on the size of the sample set (x axis) and length of the k-mers in the case of affine gap penalty: (a) k = 7; (b) k = 10; (c) k = 5; and (d) k = 15.

Figure 7

Utilization rate (y axis) depending on the size of the sample set (x axis) and length of the k-mers in the case of fixed gap penalty: (a) k = 5; (b) k = 7; (c) k = 10; and (d) k = 15.

Figure 8

Utilization rate (y axis) depending on the size of the sample set (x axis) and length of the k-mers in the case of affine gap penalty: (a) k = 5; (b) k = 7; (c) k = 10; and (d) k = 15.

Figure 9

Exact match rate (y axis) depending on the size of the sample set (x axis) and length of the k-mers in the case of fixed gap penalty: (a) k = 5; (b) k = 7; (c) k = 10; and (d) k = 15.

Figure 10

Exact match rate (y axis) depending on the size of the sample set (x axis) and length of the k-mers in the case of affine gap penalty: (a) k = 5; (b) k = 7; (c) k = 10; and (d) k = 15.