Linear-Time Sequence Comparison Using Minimal Absent Words & Applications

DOI10.1007/978-3-662-49529-2_25MaRDI QIDQ2802951zbMATH OpenOpenAlexFDO

Authors Maxime Crochemore, Gabriele Fici, Robert Mercaş, Solon P. Pissis

Publication date 3 May 2016

Published in LATIN 2016: Theoretical Informatics (Search for Journal in Brave)

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

zbMATH Keywords

absent wordsalgorithms on stringsalignment-free comparisoncircular wordsforbidden wordssequence comparison

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Abstract: Sequence comparison is a prerequisite to virtually all comparative genomic analyses. It is often realized by sequence alignment techniques, which are computationally expensive. This has led to increased research into alignment-free techniques, which are based on measures referring to the composition of sequences in terms of their constituent patterns. These measures, such as $q$-gram distance, are usually computed in time linear with respect to the length of the sequences. In this article, we focus on the complementary idea: how two sequences can be efficiently compared based on information that does not occur in the sequences. A word is an {em absent word} of some sequence if it does not occur in the sequence. An absent word is {em minimal} if all its proper factors occur in the sequence. Here we present the first linear-time and linear-space algorithm to compare two sequences by considering {em all} their minimal absent words. In the process, we present results of combinatorial interest, and also extend the proposed techniques to compare circular sequences.

Recommendations

• Alignment-free sequence comparison using absent words
• Computing DAWGs and minimal absent words in linear time for integer alphabets
• Minimal absent words in a sliding window and applications to on-line pattern matching
• Efficient computation of shortest absent words in a genomic sequence
• On the space complexity of some algorithms for sequence comparison
• Deciding context equivalence of binary overlap-free words in linear time
• scientific article; zbMATH DE number 5968858
• Study of LZ-word distribution and its application for sequence comparison
• Exact bounds on the complexity of sequential string matching algorithms

Cited in

(15)

• A simple, fast, filter-based algorithm for circular sequence comparison
• Minimal absent words in a sliding window and applications to on-line pattern matching
• Alignment-free sequence comparison using absent words
• Efficient computation of shortest absent words in complete genomes
• Absent words in a sliding window with applications
• On overabundant words and their application to biological sequence analysis
• Alignment free comparison: similarity distribution between the DNA primary sequences based on the shortest absent word
• An estimator for local analysis of genome based on the minimal absent word
• scientific article; zbMATH DE number 4128413 (Why is no real title available?)
• Using minimal absent words to build phylogeny
• Nearest constrained circular words
• Distinct squares in circular words
• Building phylogeny with minimal absent words
• Circular sequence comparison with q-grams
• Efficient computation of shortest absent words in a genomic sequence

This page was built for publication: Linear-Time Sequence Comparison Using Minimal Absent Words & Applications

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