Complexity Issues of String to Graph Approximate Matching

The problem of matching a query string to a directed graph, whose vertices are labeled by strings, has application in different fields, from data mining to computational biology. Several variants of the problem have been considered, depending on the fact that the match is exact or approximate and, i...

Descripción completa

Detalles Bibliográficos
Autores principales: Dondi, Riccardo, Mauri, Giancarlo, Zoppis, Italo
Formato: Online Artículo Texto
Lenguaje:English
Publicado: 2020
Materias:
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7206624/
http://dx.doi.org/10.1007/978-3-030-40608-0_17
_version_ 1783530445512638464
author Dondi, Riccardo
Mauri, Giancarlo
Zoppis, Italo
author_facet Dondi, Riccardo
Mauri, Giancarlo
Zoppis, Italo
author_sort Dondi, Riccardo
collection PubMed
description The problem of matching a query string to a directed graph, whose vertices are labeled by strings, has application in different fields, from data mining to computational biology. Several variants of the problem have been considered, depending on the fact that the match is exact or approximate and, in this latter case, which edit operations are considered and where are allowed. In this paper we present results on the complexity of the approximate matching problem, where edit operations are symbol substitutions and are allowed only on the graph labels or both on the graph labels and the query string. We introduce a variant of the problem that asks whether there exists a path in a graph that represents a query string with any number of edit operations and we show that is NP-complete, even when labels have length one and in the case the alphabet is binary. Moreover, when it is parameterized by the length of the input string and graph labels have length one, we show that the problem is fixed-parameter tractable and it is unlikely to admit a polynomial kernel. The NP-completeness of this problem leads to the inapproximability (within any factor) of the approximate matching when edit operations are allowed only on the graph labels. Moreover, we show that the variants of approximate string matching to graph we consider are not fixed-parameter tractable, when the parameter is the number of edit operations, even for graphs that have distance one from a DAG. The reduction for this latter result allows us to prove the inapproximability of the variant where edit operations can be applied both on the query string and on graph labels.
format Online
Article
Text
id pubmed-7206624
institution National Center for Biotechnology Information
language English
publishDate 2020
record_format MEDLINE/PubMed
spelling pubmed-72066242020-05-08 Complexity Issues of String to Graph Approximate Matching Dondi, Riccardo Mauri, Giancarlo Zoppis, Italo Language and Automata Theory and Applications Article The problem of matching a query string to a directed graph, whose vertices are labeled by strings, has application in different fields, from data mining to computational biology. Several variants of the problem have been considered, depending on the fact that the match is exact or approximate and, in this latter case, which edit operations are considered and where are allowed. In this paper we present results on the complexity of the approximate matching problem, where edit operations are symbol substitutions and are allowed only on the graph labels or both on the graph labels and the query string. We introduce a variant of the problem that asks whether there exists a path in a graph that represents a query string with any number of edit operations and we show that is NP-complete, even when labels have length one and in the case the alphabet is binary. Moreover, when it is parameterized by the length of the input string and graph labels have length one, we show that the problem is fixed-parameter tractable and it is unlikely to admit a polynomial kernel. The NP-completeness of this problem leads to the inapproximability (within any factor) of the approximate matching when edit operations are allowed only on the graph labels. Moreover, we show that the variants of approximate string matching to graph we consider are not fixed-parameter tractable, when the parameter is the number of edit operations, even for graphs that have distance one from a DAG. The reduction for this latter result allows us to prove the inapproximability of the variant where edit operations can be applied both on the query string and on graph labels. 2020-01-07 /pmc/articles/PMC7206624/ http://dx.doi.org/10.1007/978-3-030-40608-0_17 Text en © Springer Nature Switzerland AG 2020 This article is made available via the PMC Open Access Subset for unrestricted research re-use and secondary analysis in any form or by any means with acknowledgement of the original source. These permissions are granted for the duration of the World Health Organization (WHO) declaration of COVID-19 as a global pandemic.
spellingShingle Article
Dondi, Riccardo
Mauri, Giancarlo
Zoppis, Italo
Complexity Issues of String to Graph Approximate Matching
title Complexity Issues of String to Graph Approximate Matching
title_full Complexity Issues of String to Graph Approximate Matching
title_fullStr Complexity Issues of String to Graph Approximate Matching
title_full_unstemmed Complexity Issues of String to Graph Approximate Matching
title_short Complexity Issues of String to Graph Approximate Matching
title_sort complexity issues of string to graph approximate matching
topic Article
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7206624/
http://dx.doi.org/10.1007/978-3-030-40608-0_17
work_keys_str_mv AT dondiriccardo complexityissuesofstringtographapproximatematching
AT maurigiancarlo complexityissuesofstringtographapproximatematching
AT zoppisitalo complexityissuesofstringtographapproximatematching