Abstract
In this study, the problems of discovering similar and dissimilar patterns in sequence databases are discussed, and the efficient algorithms for the discovery are designed. With exponentially increasing database size and number of queries, the filtration approach, which filters out impossible patterns to accelerate similar pattern discovery, becomes more and more important in bioinformatics. However, the order of the gramsin sequences does not be considered in most of the known gram-based filtration approaches in literature so that higher false-positives would be conducted. In this study, the task of extracting similar patterns under a certain coverage level and error tolerance is transformed to a longest increasing subsequence problem with range constraints, and an efficient algorithm, Incremental Decreasing Cover Filtering (IDCF) algorithm, is designed for the filtration. Experimental results show that the IDCF algorithm significantly reduces the number of candidates for similar pattern discovery. Dissimilar patterns can be used as unique signatures to distinguish a sequence from the other sequences in a database. To achieve efficient unique signatures discovery in genomic databases, two efficient algorithms, IMUS and USD, are designed in this study. The IMUS algorithm is designed for handling a sequence database which can be loaded into internal memory, and the USD algorithm uses the IMUS algorithm as a kernel routine to handle large-scale databases. The results of our experiments present that the amount of character comparisons used in the IMUS and USD algorithms are significantly less than that of the existing discovery algorithms. On a regular PC platform, the IMUS and USD algorithms discover unique signatures from a human chromosome 11 EST database, 156M bases, within one day, and takes 35 seconds to discover signatures from a human chromosome Y EST database. The signature discovery algorithms require to set some input factors, such as signature length and mismatch tolerance, which affect the discovery results. However, suggestions about how to select proper factor values are rare, especially when an unfamiliar DNA database is used. In most cases, biologists typically select factor values based on experience, or even by guessing. If the discovered result is unsatisfactory, biologists change the input factors of the algorithm to obtain a new result. This process is repeated until a proper result is obtained. Implicit signatures under the discovery condition ( ) are defined as the signatures of length with mismatch tolerance . A discovery algorithm that could discover all implicit signatures, such that those that meet the requirements concerning the results, would be more helpful than one that depends on trial and error. However, existing discovery algorithms do not address the need to discover all implicit signatures. Two discovery algorithms, consecutive multiple discovery (CMD) algorithm and parallel and incremental signature discovery (PISD) algorithm, are proposed in this study. The PISD algorithm is designed for efficiently discovering signatures under a certain discovery condition. The algorithm finds new results by using previously discovered results as candidates, rather than by using the whole database. The PISD algorithm further increases discovery efficiency by applying parallel computing. The CMD algorithm is designed to discover implicit signatures efficiently. It uses the PISD algorithm as a kernel routine to discover implicit signatures efficiently under every feasible discovery condition. The presented CMD algorithm has up to 97% less execution time than typical sequential discovery algorithms in the discovery of implicit signatures in experiments, when eight processing cores are used.