Flanked Block-Interchange Distance on Strings

doi:10.1109/TCBB.2024.3351440

Flanked Block-Interchange Distance on Strings

2024-03-01

0

PRE

AI

DOI：10.1109/TCBB.2024.3351440

Original

Original request for help

Save

Abstract

En 中文

Rearrangement sorting problems impact profoundly in measuring genome similarities and tracing historic scenarios of species. However, recent studies on genome rearrangement mechanisms disclosed a statistically significant evidence, repeats are situated at the ends of rearrangement relevant segments and stay unchanged before and after rearrangements.To reflect the principle behind this evidence, we propose flanked block-interchange, an operation on strings that exchanges two substrings flanked by identical left and right symbols in a string. The flanked block-interchange distance problem is formulated as finding a shortest sequence of flanked block-interchanges to transform a string into the other. We propose a sufficient and necessary condition for deciding whether two strings can be transformed into each other by flanked block-interchanges. This condition is linear time verifiable. Under this condition for two strings, we present a $\text{4}\,k$4k-approximation algorithm for the flanked block-interchange distance problem where each symbol occurs at most $k$k times in a string and a polynomial algorithm for this problem where each symbol occurs at most twice in a string. We show that the problem of flanked block-interchange distance is NP-hard at last.

Keywords:

Algorithm

complexity

flanked block-interchange

genome

rearrangement

string

Flanked Block-Interchange Distance on Strings

Abstract

Journal

Organization