Your browser doesn't support javascript.
loading
Finding maximal exact matches in graphs.
Rizzo, Nicola; Cáceres, Manuel; Mäkinen, Veli.
Afiliación
  • Rizzo N; Department of Computer Science, University of Helsinki, Pietari Kalmin katu 5, P.O. Box 68, Helsinki, 00014, Finland. nicola.rizzo@helsinki.fi.
  • Cáceres M; Department of Computer Science, University of Helsinki, Pietari Kalmin katu 5, P.O. Box 68, Helsinki, 00014, Finland.
  • Mäkinen V; Department of Computer Science, University of Helsinki, Pietari Kalmin katu 5, P.O. Box 68, Helsinki, 00014, Finland.
Algorithms Mol Biol ; 19(1): 10, 2024 Mar 11.
Article en En | MEDLINE | ID: mdl-38468275
ABSTRACT

BACKGROUND:

We study the problem of finding maximal exact matches (MEMs) between a query string Q and a labeled graph G. MEMs are an important class of seeds, often used in seed-chain-extend type of practical alignment methods because of their strong connections to classical metrics. A principled way to speed up chaining is to limit the number of MEMs by considering only MEMs of length at least κ ( κ -MEMs). However, on arbitrary input graphs, the problem of finding MEMs cannot be solved in truly sub-quadratic time under SETH (Equi et al., TALG 2023) even on acyclic graphs.

RESULTS:

In this paper we show an O ( n · L · d L - 1 + m + M κ , L ) -time algorithm finding all κ -MEMs between Q and G spanning exactly L nodes in G, where n is the total length of node labels, d is the maximum degree of a node in G, m = | Q | , and M κ , L is the number of output MEMs. We use this algorithm to develop a κ -MEM finding solution on indexable Elastic Founder Graphs (Equi et al., Algorithmica 2022) running in time O ( n H 2 + m + M κ ) , where H is the maximum number of nodes in a block, and M κ is the total number of κ -MEMs. Our results generalize to the analysis of multiple query strings (MEMs between G and any of the strings). Additionally, we provide some experimental results showing that the number of graph MEMs is an order of magnitude smaller than the number of string MEMs of the corresponding concatenated collection.

CONCLUSIONS:

We show that seed-chain-extend type of alignment methods can be implemented on top of indexable Elastic Founder Graphs by providing an efficient way to produce the seeds between a set of queries and the graph. The code is available in https//github.com/algbio/efg-mems .
Palabras clave
Texto completo
Añadir a Mi BVS
Imprimir
XML
PubMed Links
Buscar en Google

Texto completo: 1 Colección: 01-internacional Base de datos: MEDLINE Idioma: En Revista: Algorithms Mol Biol Año: 2024 Tipo del documento: Article País de afiliación: Finlandia Pais de publicación: Reino Unido
Texto completo
Añadir a Mi BVS
Imprimir
XML
PubMed Links
Buscar en Google

Texto completo: 1 Colección: 01-internacional Base de datos: MEDLINE Idioma: En Revista: Algorithms Mol Biol Año: 2024 Tipo del documento: Article País de afiliación: Finlandia Pais de publicación: Reino Unido