Linear-Time Sequence Comparison Using Minimal Absent Words & Applications

Maxime Crochemore, Gabriele Fici, Robert Mercas, Solon P. Pissis

Research output: Chapter in Book/Report/Conference proceedingOther chapter contributionpeer-review

19 Citations (Scopus)
168 Downloads (Pure)

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 absent word of some sequence if it does not occur in the sequence. An absent word is 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 all their minimal absent words. In the process, we present results of combinatorial interest, and also extend the proposed techniques to compare circular sequences.
Original languageEnglish
Title of host publicationLATIN 2016: Theoretical Informatics: 12th Latin American Symposium, Ensenada, Mexico, April 11-15, 2016, Proceedings
EditorsEvangelos Kranakis, Gonzalo Navarro, Edgar Chávez
PublisherSpringer Berlin Heidelberg
Pages334-346
Number of pages13
ISBN (Print)9783662495292
DOIs
Publication statusPublished - Apr 2016

Fingerprint

Dive into the research topics of 'Linear-Time Sequence Comparison Using Minimal Absent Words & Applications'. Together they form a unique fingerprint.

Cite this