Some properties of matrix product and its applications in nonnegative tensor decomposition
Year: 2008
Journal of Information and Computing Science, Vol. 3 (2008), Iss. 4 : pp. 243–257
Abstract
In DNA related research, due to various environment conditions, mutations occur very often, where a mutation is defined as a heritable change in the DNA sequence. Therefore, approximate string matching is applied to answer those queries which find mutations. The problem of approximate string matching is that given a user specified parameter, k, we want to find where the substrings, which could have k errors at most as compared to the query sequence, occur in the database sequences. In this paper, we make use of a new index structure to support the proposed method for approximate string matching. In the proposed index structure, EII, we map each overlapping q-gram of the database sequence into an index key, and record occurring positions of the q-gram in the corresponding index entry. In the proposed method, EOB, we first generate all possible mutations for each gram in the query sequence. Then, by utilizing information recorded in the EII structure, we check both local order (i.e., the order of characters in a gram) and global order (i.e., the order of grams in an interval) of these mutations. The final answers could be determined directly without applying dynamic programming which is used in traditional filter methods for approximate string matching. From the experiment results, we show that our method could outperform the (k + s) q- samples filter, a well-known method for approximate string matching, in terms of the processing time with various conditions for short query sequences.
Journal Article Details
Publisher Name: Global Science Press
Language: English
DOI: https://doi.org/2024-JICS-22764
Journal of Information and Computing Science, Vol. 3 (2008), Iss. 4 : pp. 243–257
Published online: 2008-01
AMS Subject Headings:
Copyright: COPYRIGHT: © Global Science Press
Pages: 15