Linear-time sequence comparison using minimal absent words & applications

Maxime Crochemore; Gabriele Fici; Robert Mercaş; Solon P. Pissis

doi:10.1007/978-3-662-49529-2_25

Linear-time sequence comparison using minimal absent words & applications

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

^*Corresponding author for this work

Research output: Chapter in Book / Report / Conference proceeding › Conference contribution › Academic › peer-review

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 language	English
Title of host publication	LATIN 2016
Subtitle of host publication	Theoretical Informatics - 12th Latin American Symposium, Proceedings
Editors	Gonzalo Navarro, Evangelos Kranakis, Edgar Chávez
Publisher	Springer Verlag
Pages	334-346
Number of pages	13
ISBN (Print)	9783662495285
DOIs	https://doi.org/10.1007/978-3-662-49529-2_25
Publication status	Published - 1 Jan 2016
Externally published	Yes
Event	12th Latin American Symposium on Theoretical Informatics, LATIN 2016 - Ensenada, Mexico Duration: 11 Apr 2016 → 15 Apr 2016

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	9644
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	12th Latin American Symposium on Theoretical Informatics, LATIN 2016
Country/Territory	Mexico
City	Ensenada
Period	11/04/16 → 15/04/16

Funding

We warmly thank Alice Heliou for her inestimable code contribution and Antonio Restivo for useful discussions. Gabriele Fici?s work was supported by the PRIN 2010/2011 project ?Automi e Linguaggi Formali: Aspetti Matematici e Applicativi? of the Italian Ministry of Education (MIUR) and by the ?National Group for Algebraic and Geometric Structures, and their Applications? (GNSAGA ? INdAM). Robert Merca?s?s work was supported by the P.R.I.M.E. programme of DAAD co-funded by BMBF and EU?s 7th Framework Programme (grant 605728). Solon P. Pissis?s work was supported by a Research Grant (#RG130720) awarded by the Royal Society

Keywords

Absent words
Algorithms on strings
Alignmentfree comparison
Circular words
Forbidden words
Sequence comparison

Access to Document

10.1007/978-3-662-49529-2_25

Persistent URL (handle)

Persistent link

Cite this

Crochemore, M., Fici, G., Mercaş, R., & Pissis, S. P. (2016). Linear-time sequence comparison using minimal absent words & applications. In G. Navarro, E. Kranakis, & E. Chávez (Eds.), LATIN 2016: Theoretical Informatics - 12th Latin American Symposium, Proceedings (pp. 334-346). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9644). Springer Verlag. https://doi.org/10.1007/978-3-662-49529-2_25

Crochemore, Maxime ; Fici, Gabriele ; Mercaş, Robert et al. / Linear-time sequence comparison using minimal absent words & applications. LATIN 2016: Theoretical Informatics - 12th Latin American Symposium, Proceedings. editor / Gonzalo Navarro ; Evangelos Kranakis ; Edgar Chávez. Springer Verlag, 2016. pp. 334-346 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{21057eb9f8fd43b6981f923c7d0819e0,

title = "Linear-time sequence comparison using minimal absent words & applications",

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.",

keywords = "Absent words, Algorithms on strings, Alignmentfree comparison, Circular words, Forbidden words, Sequence comparison",

author = "Maxime Crochemore and Gabriele Fici and Robert Merca{\c s} and Pissis, {Solon P.}",

year = "2016",

month = jan,

day = "1",

doi = "10.1007/978-3-662-49529-2_25",

language = "English",

isbn = "9783662495285",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "334--346",

editor = "Gonzalo Navarro and Evangelos Kranakis and Edgar Ch{\'a}vez",

booktitle = "LATIN 2016",

address = "Germany",

note = "12th Latin American Symposium on Theoretical Informatics, LATIN 2016 ; Conference date: 11-04-2016 Through 15-04-2016",

}

Crochemore, M, Fici, G, Mercaş, R & Pissis, SP 2016, Linear-time sequence comparison using minimal absent words & applications. in G Navarro, E Kranakis & E Chávez (eds), LATIN 2016: Theoretical Informatics - 12th Latin American Symposium, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9644, Springer Verlag, pp. 334-346, 12th Latin American Symposium on Theoretical Informatics, LATIN 2016, Ensenada, Mexico, 11/04/16. https://doi.org/10.1007/978-3-662-49529-2_25

Linear-time sequence comparison using minimal absent words & applications. / Crochemore, Maxime; Fici, Gabriele; Mercaş, Robert et al.
LATIN 2016: Theoretical Informatics - 12th Latin American Symposium, Proceedings. ed. / Gonzalo Navarro; Evangelos Kranakis; Edgar Chávez. Springer Verlag, 2016. p. 334-346 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9644).

Research output: Chapter in Book / Report / Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Linear-time sequence comparison using minimal absent words & applications

AU - Crochemore, Maxime

AU - Fici, Gabriele

AU - Mercaş, Robert

AU - Pissis, Solon P.

PY - 2016/1/1

Y1 - 2016/1/1

N2 - 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.

AB - 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.

KW - Absent words

KW - Algorithms on strings

KW - Alignmentfree comparison

KW - Circular words

KW - Forbidden words

KW - Sequence comparison

UR - http://www.scopus.com/inward/record.url?scp=84961751346&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84961751346&partnerID=8YFLogxK

U2 - 10.1007/978-3-662-49529-2_25

DO - 10.1007/978-3-662-49529-2_25

M3 - Conference contribution

AN - SCOPUS:84961751346

SN - 9783662495285

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 334

EP - 346

BT - LATIN 2016

A2 - Navarro, Gonzalo

A2 - Kranakis, Evangelos

A2 - Chávez, Edgar

PB - Springer Verlag

T2 - 12th Latin American Symposium on Theoretical Informatics, LATIN 2016

Y2 - 11 April 2016 through 15 April 2016

ER -

Crochemore M, Fici G, Mercaş R, Pissis SP. Linear-time sequence comparison using minimal absent words & applications. In Navarro G, Kranakis E, Chávez E, editors, LATIN 2016: Theoretical Informatics - 12th Latin American Symposium, Proceedings. Springer Verlag. 2016. p. 334-346. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-662-49529-2_25

Linear-time sequence comparison using minimal absent words & applications

Abstract

Publication series

Conference

Funding

Keywords

Access to Document

Persistent URL (handle)

Other files and links

Fingerprint

Cite this