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(m^2)-space, for a character sequence of size n and pattern of size m. This improves upon a previous O(nm^2)-time algorithm.
Efficient Matching of Biological Sequences Allowing for Non-Overlapping Inversions
CANTONE, Domenico;FARO, SIMONE
2011-01-01
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(m^2)-space, for a character sequence of size n and pattern of size m. This improves upon a previous O(nm^2)-time algorithm.File in questo prodotto:
| File | Dimensione | Formato | |
|---|---|---|---|
|
2011 CantoneCristofaroFaro CPM.pdf
solo gestori archivio
Tipologia:
Versione Editoriale (PDF)
Licenza:
Non specificato
Dimensione
223.62 kB
Formato
Adobe PDF
|
223.62 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
