Elastic founder graphs improved and enhanced

DOI10.1016/j.tcs.2023.114269arXiv2303.05336MaRDI QIDQ6199393

Nicola Rizzo, Veli Mäkinen, Tuukka Norri, Massimo Equi

Publication date: 23 February 2024

Published in: Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

multiple sequence alignmentpattern matchingsegmentation algorithmsuffix treedocument listing

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails
• Linear bidirectional on-line construction of affix trees
• On-line construction of suffix trees
• Linear time construction of indexable elastic founder graphs
• The affix array data structure and its applications to RNA secondary structure analysis
• Suffix Arrays: A New Method for On-Line String Searches
• Algorithms on Strings, Trees and Sequences
• Sparse Dynamic Programming on DAGs with Small Width
• Linear-time String Indexing and Analysis in Small Space
• Comparing Degenerate Strings
• Linear-time computation of DAWGs, symmetric indexing structures, and MAWs for integer alphabets
• Algorithms and complexity on indexing founder graphs

This page was built for publication: Elastic founder graphs improved and enhanced