Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Alignment-free sequence comparison using absent words   Sequence comparison is a prerequisite to virtually all comparative genomic
analyses. It is often realised 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 paper, 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. We also present an algorithm that, given a word $x$
of length $n$, computes the largest integer for which all factors of $x$ of
that length occur in some minimal absent word of $x$ in time and space
$\cO(n)$. Finally, we show that the known asymptotic upper bound on the number
of minimal absent words of a word is tight.

11
The categories of this paper are: hep-lat
16
The categories of this paper are: stat
21
The categories of this paper are: adap-org
7
The categories of this paper are: hep-th
3
The categories of this paper are: physics
0
The categories of this paper are: hep-ph
8
The categories of this paper are: hep-ex
15
The categories of this paper are: nucl-ex
27
The categories of this paper are: comp-gas
35
The categories of this paper are: mtrl-th
19
The categories of this paper are: eess
20
The categories of this paper are: acc-phys
22
The categories of this paper are: chao-dyn
25
The categories of this paper are: patt-sol
23
The categories of this paper are: solv-int
31
The categories of this paper are: ao-sci