License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.WABI.2020.19
URN: urn:nbn:de:0030-drops-128086
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12808/
Cantone, Domenico ;
Faro, Simone ;
Pavone, Arianna
Sequence Searching Allowing for Non-Overlapping Adjacent Unbalanced Translocations
Abstract
Unbalanced translocations are among the most frequent chromosomal alterations, accounted for 30% of all losses of heterozygosity, a major genetic event causing inactivation of tumor suppressor genes. Despite of their central role in genomic sequence analysis, little attention has been devoted to the problem of matching sequences allowing for this kind of chromosomal alteration.
In this paper we investigate the approximate string matching problem when the edit operations are non-overlapping unbalanced translocations of adjacent factors. In particular, we first present a ?(nm³)-time and ?(m²)-space algorithm based on the dynamic-programming approach. Then we improve our first result by designing a second solution which makes use of the Directed Acyclic Word Graph of the pattern. In particular, we show that under the assumptions of equiprobability and independence of characters, our algorithm has a ?(nlog²_{σ} m) average time complexity, for an alphabet of size σ, still maintaining the ?(nm³)-time and the ?(m²)-space complexity in the worst case. To the best of our knowledge this is the first solution in literature for the approximate string matching problem allowing for unbalanced translocations of factors.
BibTeX - Entry
@InProceedings{cantone_et_al:LIPIcs:2020:12808,
author = {Domenico Cantone and Simone Faro and Arianna Pavone},
title = {{Sequence Searching Allowing for Non-Overlapping Adjacent Unbalanced Translocations}},
booktitle = {20th International Workshop on Algorithms in Bioinformatics (WABI 2020)},
pages = {19:1--19:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-161-0},
ISSN = {1868-8969},
year = {2020},
volume = {172},
editor = {Carl Kingsford and Nadia Pisanti},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12808},
URN = {urn:nbn:de:0030-drops-128086},
doi = {10.4230/LIPIcs.WABI.2020.19},
annote = {Keywords: Text processing, approximate matching, inversions, sequence matching}
}
|
Keywords: |
|
Text processing, approximate matching, inversions, sequence matching |
|
Collection: |
|
20th International Workshop on Algorithms in Bioinformatics (WABI 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
25.08.2020 |
