Efficient computation of sequence mappability

DOI10.1007/s00453-022-00934-yOpenAlexW4210367916MaRDI QIDQ2134748

Juliusz Straszyński, Panagiotis Charalampopoulos, Solon P. Pissis, Costas S. Iliopoulos, Tomasz Kociumaka, Jakub Radoszewski

Publication date: 3 May 2022

Published in: Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

Hamming distance\(k\)-errata treesequence mappability

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Efficient string matching with k mismatches
• Parallel string matching with k mismatches
• Which problems have strongly exponential complexity?
• Applying the positional Burrows-Wheeler transform to all-pairs Hamming distance
• Longest common substrings with \(k\) mismatches
• Longest common substring with approximately \(k\) mismatches
• Longest Common Prefix with Mismatches
• Suffix Arrays: A New Method for On-Line String Searches
• Linear work suffix array construction
• Dictionary matching and indexing with errors and don't cares
• Efficient randomized pattern-matching algorithms
• Longest Common Prefixes with k-Mismatches and Applications
• Linear-Time Algorithm for Long LCF with k Mismatches
• On the sorting-complexity of suffix tree construction
• Lowest common ancestors in trees and directed acyclic graphs
• Algorithmic Framework for Approximate Matching Under Bounded Edits with Applications to Sequence Analysis
• Faster algorithms for 1-mappability of a sequence
• On the complexity of \(k\)-SAT
• Efficient computation of sequence mappability
• Longest common prefixes with \(k\)-errors and applications