Generic placeholder image

Current Bioinformatics


ISSN (Print): 1574-8936
ISSN (Online): 2212-392X

Research Article

Fast and Practical Algorithms for Searching the Gapped Palindromes

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

Volume 12 , Issue 3 , 2017

Page: [225 - 232] Pages: 8

DOI: 10.2174/1574893610666150828193203

Price: $65


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.

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

Graphical Abstract

Rights & Permissions Print Export Cite as
© 2022 Bentham Science Publishers | Privacy Policy