Thumbnail
Access Restriction
Subscribed

Author Mohanty, Pragyan Sheela ♦ Tragoudas, Spyros
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2014
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Boolean functions ♦ DNA sequence ♦ Binary decision diagrams ♦ Pattern matching algorithms
Abstract Searching for a particular pattern in a very large DNA database is a fundamental and essential component in computational biology. In the biological world, pattern matching is required for finding repeats in a particular DNA sequence, finding motif, aligning sequences, and other similar tasks. Due to an immense amount and continuous increase of biological data, the searching process requires very fast algorithms. A function-based tool set for fast offline pattern searches in large DNA sequences is proposed. The method benefits from the use of Boolean functions, their compact storage using canonical data structure, and the existence of built-in operators for these data structures. Experiments on DNA sequences from the NCBI database show that the proposed approach is scalable. The time complexity depends on the size of the data structure used for storing the function that represents the DNA sequence. It is shown that the presented approach exhibits sublinear time complexity to the DNA sequence size.
ISSN 15504832
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2014-11-01
Publisher Place New York
e-ISSN 15504840
Journal ACM Journal on Emerging Technologies in Computing Systems (JETC)
Volume Number 11
Issue Number 2
Page Count 25
Starting Page 1
Ending Page 25


Open content in new tab

   Open content in new tab
Source: ACM Digital Library