Inversions are a class of chromosomal mutations, widely regarded as one of the major mechanisms for reorganizing the genome. In this paper we present a new algorithm for the approximate string matching problem allowing for non-overlapping inversions which runs in O(nm) worst-case time and O(m2) space, for a character sequence of size n and pattern of size m. This improves upon a previous O(nm2)-time algorithm. In addition we present a variant of our algorithm with the same complexity in the worst case, but with a O(n) time complexity in the average case. This work has been supported by Istituto Nazionale di Alta Matematica "Francesco Severi".

Efficient string-matching allowing for non-overlapping inversions

CANTONE, Domenico;FARO, SIMONE
2013

Abstract

Inversions are a class of chromosomal mutations, widely regarded as one of the major mechanisms for reorganizing the genome. In this paper we present a new algorithm for the approximate string matching problem allowing for non-overlapping inversions which runs in O(nm) worst-case time and O(m2) space, for a character sequence of size n and pattern of size m. This improves upon a previous O(nm2)-time algorithm. In addition we present a variant of our algorithm with the same complexity in the worst case, but with a O(n) time complexity in the average case. This work has been supported by Istituto Nazionale di Alta Matematica "Francesco Severi".
File in questo prodotto:
Non ci sono file associati a questo prodotto.

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: http://hdl.handle.net/20.500.11769/13303
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 21
  • ???jsp.display-item.citation.isi??? 17
social impact