New Approaches for Analyzing Recombinations of Biological Sequences

Recombination is one of the most important mechanisms of genomic mutation.
Recent work has revealed that recombinations occur far more frequently than
previously thought in sequences such as RNA sequences of human immunodeficiency
viruses (HIVs).
But existing techniques for detecting recombinations of sequences
are inaccurate or impractical.
For this problem, we propose two kinds of
approaches. One is an approach by the alignment of sequences
considering recombinations, and the
other is a statistical approach that detects recombinations using aligned
multiple sequences.

For the first approach by the alignment technique,
we first formulate an alignment problem for sequences containing recombinations.
We then give algorithms with practical bounds for various versions
of the problem.
In the statistical approach, we consider a simple model of the statistical behavior
of point mutations, and propose a method for detecting recombinations by computing
what we call $z$-values.

To demonstrate both techniques, we conducted experiments using actual RNA sequences
of HIVs and artificially recombined sequence data.