Algorithms and complexity on indexing founder graphs

DOI10.1007/s00453-022-01007-warXiv2102.12822MaRDI QIDQ6103519

Veli Mäkinen, Alexandru I. Tomescu, Jarno Alanko, Tuukka Norri, Bastien Cazaux, Massimo Equi

Publication date: 5 June 2023

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2102.12822

zbMATH Keywords

computational complexitygraph algorithmsmultiple sequence alignmentstring matchingcompressed data structuressegmentation algorithmspangenomics

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Related Items (2)

On the Complexity of String Matching for Graphs ⋮ Elastic founder graphs improved and enhanced

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• FM-index of alignment: a compressed index for similar strings
• Bidirectional search in a string with wavelet trees and bidirectional matching statistics
• Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails
• Wheeler graphs: a framework for BWT-based data structures
• FM-index of alignment with gaps
• Efficient pattern matching in elastic-degenerate strings
• Linear time construction of indexable elastic founder graphs
• Approximate pattern matching on elastic-degenerate text
• Indexing hypertext
• Compressed suffix trees with full functionality
• A new algorithm for optimal 2-constraint satisfaction and its implications
• Versatile Succinct Representations of the Bidirectional Burrows-Wheeler Transform
• Suffix Tree of Alignment: An Efficient Index for Similar Data
• Suffix Arrays: A New Method for On-Line String Searches
• Efficient string matching
• The Complexity of Some Problems on Subsequences and Supersequences
• Pattern Matching in Hypertext
• Linear-time String Indexing and Analysis in Small Space
• Comparing Degenerate Strings
• On the Hardness and Inapproximability of Recognizing Wheeler Graphs
• Fully Functional Suffix Trees and Optimal Text Searching in BWT-Runs Bounded Space
• Faster Online Elastic Degenerate String Matching
• Regular Languages meet Prefix Sorting
• Pattern Matching on Elastic-Degenerate Text with Errors
• Truly Subquadratic-Time Extension Queries and Periodicity Detection in Strings with Uncertainties.
• On the complexity of \(k\)-SAT

This page was built for publication: Algorithms and complexity on indexing founder graphs