Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Optimal alignments of longest common subsequences and their path
  properties   We investigate the behavior of optimal alignment paths for homologous
(related) and independent random sequences. An alignment between two finite
sequences is optimal if it corresponds to the longest common subsequence (LCS).
We prove the existence of lowest and highest optimal alignments and study their
differences. High differences between the extremal alignments imply the high
variety of all optimal alignments. We present several simulations indicating
that the homologous (having the same common ancestor) sequences have typically
the distance between the extremal alignments of much smaller size than
independent sequences. In particular, the simulations suggest that for the
homologous sequences, the growth of the distance between the extremal
alignments is logarithmical. The main theoretical results of the paper prove
that (under some assumptions) this is the case, indeed. The paper suggests that
the properties of the optimal alignment paths characterize the relatedness of
the sequences.

14
The categories of this paper are: math-ph
33
The categories of this paper are: plasm-ph
31
The categories of this paper are: ao-sci
12
The categories of this paper are: nucl-th
34
The categories of this paper are: chem-ph
7
The categories of this paper are: hep-th
6
The categories of this paper are: astro-ph
27
The categories of this paper are: comp-gas
28
The categories of this paper are: alg-geom
4
The categories of this paper are: cond-mat
3
The categories of this paper are: physics
5
The categories of this paper are: gr-qc
0
The categories of this paper are: hep-ph
9
The categories of this paper are: nlin
35
The categories of this paper are: mtrl-th
15
The categories of this paper are: nucl-ex