{'fraction_non_alphanumeric': 0.022935779816513763, 'fraction_numerical': 0.0024700070571630206, 'mean_word_length': 5.532258064516129, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Parallel Implementation of the Smith-Waterman Algorithm for Large Scale Database Search

Database search is the most heavily used operation in computational biology nowadays. It reports local alignments that may reveal homologous groups of sequences thereby helping on determining the function of new sequences. Database search is achieved by applying a basic operation, known as pairwise sequence comparison, repeatedly to the query sequence against each sequence in the database. Given the large, and increasing, number of sequences in current databases, the performance of this basic operation has become critical. The Smith-Waterman algorithm [1] produces optimal results for this basic operation but it is not commonly used due to its quadratic time complexity. Instead, faster methods, providing approximated solutions (e.g. BLAST, FASTA), are preferred for its almost linear time complexity. The use of parallel processing has brought some hope on improving the performance of the pairwise sequence comparison operation when using the Smith-Waterman algorithm. However, the exploitation of parallelism at this intra-sequence level has been showed to produce good speedups only when dealing with long sequences [2]. Parallel processing has also been used in the database search problem [3]. But in this case, each processor is usually responsible for performing a number of comparisons independently from each other instead of cooperating to compare every sequence in the database. Parallel implementations exploiting this inter-sequence level of parallelism have its performance dependent on the length of the sequences. Dynamic load balancing strategies have been proposed to minimize this problem, however, none is able to produce good results when sequence lengths vary greatly [4]. Current genome projects generate a considerable number of DNA data whose processing requires a large scale database search, i.e. multiple database search operations have to be performed frequently. In this work, we propose and implement a strategy to carry out parallel database searches with multiple query sequences using the Smith-Waterman algorithm, optimized according to Gotoh [5]. This is achieved by concatenating both query and database sequences, and processing the resulting similarity matrices and alignments in parallel. Processors cooperate when calculating alignments crossing its boundaries and an efficient scheduling algorithm is used to increase processor utilization. The implementation is based on the Message Passing Interface (MPI) library and has been tested on a cluster of PCs. Preliminary results show more accurate alignments (compared to BLAST), good speedup (approximately 4 on 6 nodes) and better performance than traditional inter-sequence parallel implementations when comparing sequences of varying lengths.