Fast and Practical Algorithms for Searching the Gapped Palindromes

Title:Fast and Practical Algorithms for Searching the Gapped Palindromes

Volume: 12 Issue: 3

Author(s): Shivika Gupta*, Rajesh Prasad and Sunita Yadav

Affiliation:

• Department of Computer Science & Engineering, Ajay Kumar Garg Engineering College, 27th km Stone, Delhi- Hapur Bypass, Ghaziabad-201009,India

Keywords: Palindromes, gapped palindromes, biological gapped palindromes, long armed, length constrained, enhanced suffix array.

Abstract: Background: The remarkable gapped palindrome structures can have profound effects on chromosomes and are responsible for neurological diseases in humans. Gapped palindromes refer to the palindromes that have a space (set of characters) between the left and right palindromic arms of the string. Gapped palindromes are divided into two classes: long armed and length constrained.

Objective: In practical applications such as DNA sequence analysis, it is desired to cope with the performance of gapped palindromes.

Method: This paper presents efficient algorithms of O(n) for solving both types of gapped palindrome problem in biological sequences using enhanced suffix array.

Results: Experimental results show that our algorithms are space efficient, faster and easy to implement. We have also provided an open source standalone application called fapa-gp for searching different classes of gapped palindromes in genome sequences. It includes source codes of the proposed algorithm, standalone application and other supplementary materials.

Conclusion: The presented algorithms ensure finding long armed and length constrained versions of gapped palindromes in the biological DNA sequence, verifying all the conditions. Our algorithms analyzed short DNA sequences easily.

Cite this article as:

Gupta Shivika*, Prasad Rajesh and Yadav Sunita, Fast and Practical Algorithms for Searching the Gapped Palindromes, Current Bioinformatics 2017; 12 (3) . https://dx.doi.org/10.2174/1574893610666150828193203

DOI https://dx.doi.org/10.2174/1574893610666150828193203	Print ISSN 1574-8936
Publisher Name Bentham Science Publisher	Online ISSN 2212-392X