Linear time construction of indexable elastic founder graphs

DOI10.1007/978-3-031-06678-8_35MaRDI QIDQ2169983zbMATH OpenOpenAlexFDO

Authors Nicola Rizzo, Veli Mäkinen

Publication date 30 August 2022

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

zbMATH Keywords

dynamic programmingdata structurespattern matchingsuffix treemultiple sequence alignmentsegmentation algorithms

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Discrete mathematics in relation to computer science (68Rxx)

Recommendations

• Linear time construction of indexable founder block graphs
• Algorithms and complexity on indexing founder graphs
• scientific article; zbMATH DE number 7696008
• Optimal query complexity bounds for finding graphs
• scientific article; zbMATH DE number 6004055
• On indexable graphs
• Embedding rectilinear graphs in linear time
• scientific article; zbMATH DE number 7301806
• An Almost Linear-Time Algorithm for Graph Realization
• Finding articulation points of large graphs in linear time

Cites work

• scientific article; zbMATH DE number 7561548 (Why is no real title available?)
• Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails
• Linear time construction of indexable founder block graphs
• On-line construction of suffix trees

Cited in

(2)

• Algorithms and complexity on indexing founder graphs
• Elastic founder graphs improved and enhanced

Describes a project that uses

Uses Software

• HISAT
• vg

This page was built for publication: Linear time construction of indexable elastic founder graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2169983)