Publication Type:

Conference Paper

Source:

International Conference on Bioinformatics & Computational Biology, BIOCOMP 2010 (2010)

URL:

https://www.researchgate.net/profile/Bhadrachalam_Chitturi/publication/221051667_Prefix_Reversals_on_Strings/links/57b4521008aeddbf36e6da4b.pdf

Abstract:

A reversal is an operation that reverses a substring. When the chosen substring is restricted to a prefix it is called a prefix reversal. Given two strings, α and β, the problem of finding the minimum number of prefix reversals that transform α into β is called the prefix reversal distance problem. This problem is a version of the reversal distance problem, related to genetic rearrangements. An upper bound of 18n/11 and a lower bound of 15n/14 are known for permutations. We give bounds for prefix reversals on strings. For example, n-1 prefix reversals are sufficient to transform a given n-binary string into a compatible string, i.e. a string with same frequency for each symbol as the given string. We also prove that the prefix reversal distance for strings is NP-complete.

Cite this Research Publication

Dr. Bhadrachalam Chitturi and Sudborough, I. Hal, “Prefix Reversals on Strings”, in International Conference on Bioinformatics & Computational Biology, BIOCOMP 2010, 2010.

207
PROGRAMS
OFFERED
5
AMRITA
CAMPUSES
15
CONSTITUENT
SCHOOLS
A
GRADE BY
NAAC, MHRD
8th
RANK(INDIA):
NIRF 2018
150+
INTERNATIONAL
PARTNERS