A New Algorithm for Fast All-Against-All Substring Matching

We present a new and efficient algorithm to solve the ’threshold all vs. all’ problem, which involves searching of two strings (with length N and M respectively) for finding all maximal approximate matches of length at least S and with up to K differences. The algorithm is based on a novel graph mod...

Descripción completa

Detalles Bibliográficos
Autores principales: Barsky, Marina, Stege, Ulrike, Thomo, Alex, Upton, Chris
Formato: Online Artículo Texto
Lenguaje:English
Publicado: 2006
Materias:
Article
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7120239/
http://dx.doi.org/10.1007/11880561_31
_version_ 1783514932035190784
author Barsky, Marina
Stege, Ulrike
Thomo, Alex
Upton, Chris
author_facet Barsky, Marina
Stege, Ulrike
Thomo, Alex
Upton, Chris
author_sort Barsky, Marina
collection PubMed
description We present a new and efficient algorithm to solve the ’threshold all vs. all’ problem, which involves searching of two strings (with length N and M respectively) for finding all maximal approximate matches of length at least S and with up to K differences. The algorithm is based on a novel graph model, and it solves the problem in time O(NMK (2)).
format Online
Article
Text
id pubmed-7120239
institution National Center for Biotechnology Information
language English
publishDate 2006
record_format MEDLINE/PubMed
spelling pubmed-71202392020-04-06 A New Algorithm for Fast All-Against-All Substring Matching Barsky, Marina Stege, Ulrike Thomo, Alex Upton, Chris String Processing and Information Retrieval Article We present a new and efficient algorithm to solve the ’threshold all vs. all’ problem, which involves searching of two strings (with length N and M respectively) for finding all maximal approximate matches of length at least S and with up to K differences. The algorithm is based on a novel graph model, and it solves the problem in time O(NMK (2)). 2006 /pmc/articles/PMC7120239/ http://dx.doi.org/10.1007/11880561_31 Text en © Springer-Verlag Berlin Heidelberg 2006 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
Barsky, Marina
Stege, Ulrike
Thomo, Alex
Upton, Chris
A New Algorithm for Fast All-Against-All Substring Matching
title A New Algorithm for Fast All-Against-All Substring Matching
title_full A New Algorithm for Fast All-Against-All Substring Matching
title_fullStr A New Algorithm for Fast All-Against-All Substring Matching
title_full_unstemmed A New Algorithm for Fast All-Against-All Substring Matching
title_short A New Algorithm for Fast All-Against-All Substring Matching
title_sort new algorithm for fast all-against-all substring matching
topic Article
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7120239/
http://dx.doi.org/10.1007/11880561_31
work_keys_str_mv AT barskymarina anewalgorithmforfastallagainstallsubstringmatching
AT stegeulrike anewalgorithmforfastallagainstallsubstringmatching
AT thomoalex anewalgorithmforfastallagainstallsubstringmatching
AT uptonchris anewalgorithmforfastallagainstallsubstringmatching
AT barskymarina newalgorithmforfastallagainstallsubstringmatching
AT stegeulrike newalgorithmforfastallagainstallsubstringmatching
AT thomoalex newalgorithmforfastallagainstallsubstringmatching
AT uptonchris newalgorithmforfastallagainstallsubstringmatching

Ejemplares similares