An edit distance is a metric between words that quantifies how two words differ by counting the number of edit operations needed to transform one word into the other one. A word f is said isometric with respect to an edit distance if, for any pair of f-free words u and v, there exists a transformation of minimal length from u to v via the related edit operations such that all the intermediate words are also f-free. The adjective “isometric” comes from the fact that, if the Hamming distance is considered (i.e., only mismatches), then isometric words define some isometric subgraphs of hypercubes. We consider the case of edit distance with swap and mismatch. We compare it with the case of mismatch only and prove some properties of isometric words that are related to particular features of their overlaps.

Anselmo, M., Castiglione, G., Flores, M., Giammarresi, D., Madonia, M., Mantaci, S. (2023). Isometric Words Based on Swap and Mismatch Distance. In F. Drewes, M. Volkov (a cura di), Isometric Words Based on Swap and Mismatch Distance (pp. 23-35) [10.1007/978-3-031-33264-7_3].

Isometric Words Based on Swap and Mismatch Distance

Castiglione, G.
;
Flores, M.
;
Mantaci, S.
2023-01-01

Abstract

An edit distance is a metric between words that quantifies how two words differ by counting the number of edit operations needed to transform one word into the other one. A word f is said isometric with respect to an edit distance if, for any pair of f-free words u and v, there exists a transformation of minimal length from u to v via the related edit operations such that all the intermediate words are also f-free. The adjective “isometric” comes from the fact that, if the Hamming distance is considered (i.e., only mismatches), then isometric words define some isometric subgraphs of hypercubes. We consider the case of edit distance with swap and mismatch. We compare it with the case of mismatch only and prove some properties of isometric words that are related to particular features of their overlaps.
2023
978-3-031-33263-0
978-3-031-33264-7
Anselmo, M., Castiglione, G., Flores, M., Giammarresi, D., Madonia, M., Mantaci, S. (2023). Isometric Words Based on Swap and Mismatch Distance. In F. Drewes, M. Volkov (a cura di), Isometric Words Based on Swap and Mismatch Distance (pp. 23-35) [10.1007/978-3-031-33264-7_3].
File in questo prodotto:
File Dimensione Formato  
dlt.pdf

Solo gestori archvio

Tipologia: Versione Editoriale
Dimensione 285.81 kB
Formato Adobe PDF
285.81 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10447/592394
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? ND
social impact