Linear time construction of indexable founder block graphs

DOI10.4230/LIPICS.WABI.2020.7MaRDI QIDQ6487631zbMATH OpenFDO

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

Publication date 7 February 2023

Full work available at URL https://doi.org/10.4230/LIPICS.WABI.2020.7

zbMATH Keywords

compressed data structuresfounder reconstructionmultiple sequence alignmentpangenome indexingstring matching

Mathematics Subject Classification ID

Computational methods for problems pertaining to biology (92-08) Genetics and epigenetics (92D10) Protein sequences, DNA sequences (92D20)

Recommendations

• Minimum segmentation for pan-genomic founder reconstruction in linear time
• Efficient construction of a compressed de Bruijn graph for pan-genome analysis
• scientific article; zbMATH DE number 1945170
• Linking indexing data structures to de Bruijn graphs: construction and update
• Indexing variation graphs

Cites work

• Bidirectional search in a string with wavelet trees and bidirectional matching statistics
• Bidirectional Variable-Order de Bruijn Graphs
• Degenerate string comparison and applications
• Efficient string matching
• Even faster elastic-degenerate string matching via fast matrix multiplication
• Fast matching statistics in small space
• scientific article; zbMATH DE number 1945170 (Why is no real title available?)
• scientific article; zbMATH DE number 7559178 (Why is no real title available?)
• Indexing hypertext
• Linear-time string indexing and analysis in small space
• On the complexity of string matching for graphs
• On the Hardness and Inapproximability of Recognizing Wheeler Graphs
• Regular Languages meet Prefix Sorting
• Succinct de Bruijn graphs
• Suffix Arrays: A New Method for On-Line String Searches
• Wheeler graphs: a framework for BWT-based data structures

Cited in

(15)

• Linear time construction of indexable elastic founder graphs
• Efficient construction of a compressed de Bruijn graph for pan-genome analysis
• Minimum segmentation for pan-genomic founder reconstruction in linear time
• PanCake: a data structure for pangenomes
• Elastic-Degenerate String Matching via Fast Matrix Multiplication
• Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails
• Algorithms and complexity on indexing founder graphs
• Elastic founder graphs improved and enhanced
• Linear time maximum segmentation problems in column stream model
• Wheeler maps
• Elastic-degenerate string matching with 1 error or mismatch
• A unifying taxonomy of pattern matching in degenerate strings and founder graphs
• Elastic-degenerate string comparison
• Faster approximate elastic-degenerate string matching. Part B
• Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails

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

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