Publication Type:

Book Chapter

Source:

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Springer Berlin Heidelberg, Volume 5092, Berlin, Heidelberg, p.299–308 (2008)

ISBN:

9783540697336

URL:

https://www.scopus.com/record/display.uri?eid=2-s2.0-48249121100&origin=resultslist&sort=plf-f&src=s&st1=Adjacent+Swaps+on+Strings&st2=&sid=03bfd41c6d03e530d53cd7bf674e7562&sot=b&sdt=b&sl=40&s=TITLE-ABS-KEY%28Adjacent+Swaps+on+Strings%29&relpos=7&citeCnt=

Keywords:

Biochemistry, Combinatorics, Feature extraction, International conferences, molecular biology, Music theory, Pattern recognition

Abstract:

Transforming strings by exchanging elements at bounded distance is applicable in fields like molecular biology, pattern recognition and music theory. A reversal of length two at position i is denoted by (i i+1). When it is applied to π, where π = π 1,π 2, π 3,..., π i ,π i∈+∈1, π n , it transforms π to π′, where π′ = π 1,π 2, π 3,..., π i∈-∈1,π i∈+∈1, π i , π i∈+∈1, ..., π n . We call this operation an adjacent swap. We study the problem of computing the minimum number of adjacent swaps needed to transform one string of size n into another compatible string over an alphabet σ of size k, i.e. adjacent swap distance problem. O(nlog 2 n) time complexity algorithms are known for adjacent swap distance. We give an algorithm with O(nk) time for both signed and unsigned versions of this problem where k is the number of symbols. We also give an algorithm with O(nk) time for transforming signed strings with reversals of length up to 2, i.e. reversals of length 1 or 2. © 2008 Springer-Verlag Berlin Heidelberg.

Cite this Research Publication

Dr. Bhadrachalam Chitturi, Sudborough, H., Voit, W., and Feng, X., “Adjacent Swaps on Strings”, in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5092, X. Hu and Wang, J. Berlin, Heidelberg: Springer Berlin Heidelberg, 2008, pp. 299–308.

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