Implementation of Aligner. More...
#include <aligner_impl.hh>
Classes | |
class | ModifiedScoringView |
Provides a modified view on the scoring. More... | |
class | UnmodifiedScoringView |
Provides the standard view on the scoring. More... | |
Public Types | |
enum | { E_NO_NO, E_X_NO, E_NO_X, E_X_X, E_OP_NO, E_NO_OP, E_OP_X, E_X_OP } |
different states for computation of structure-local alignment. More... | |
typedef ScoreMatrix | M_matrix_t |
typedef BasePairs__Arc | Arc |
an arc | |
Public Member Functions | |
AlignerImpl (const AlignerImpl &a) | |
copy constructor | |
AlignerImpl (const Sequence &seqA, const Sequence &seqB, const ArcMatches &arc_matches, const AlignerParams *ap, const Scoring *s) | |
Construct from parameters. | |
~AlignerImpl () | |
template<class ScoringView > | |
void | init_state (int state, pos_type al, pos_type ar, pos_type bl, pos_type br, bool globalA, bool exclA, bool globalB, bool exclB, ScoringView sv) |
initialize matrices M and E | |
template<class ScoringView > | |
infty_score_t | align_noex (int state, pos_type al, pos_type bl, pos_type i, pos_type j, ScoringView sv) |
standard cases for alignment (without exlusion handling). | |
void | align_in_arcmatch (pos_type al, pos_type ar, pos_type bl, pos_type br, bool allow_exclusion) |
infty_score_t | align_top_level_free_endgaps () |
template<class ScoringView > | |
infty_score_t | align_top_level_locally (ScoringView sv) |
template<class ScoringView > | |
void | trace_in_arcmatch (int state, int al, int i, int bl, int j, bool top_level, ScoringView sv) |
align top level in the scanning version | |
template<class ScoringView > | |
void | trace_noex (int state, pos_type al, pos_type i, pos_type bl, pos_type j, bool top_level, ScoringView sv) |
standard cases in trace back (without handling of exclusions) | |
void | trace_arcmatch (const ArcMatch &am) |
void | trace_arcmatch_noLP (const ArcMatch &am) |
infty_score_t | align () |
compute the alignment score | |
void | align_D () |
void | fill_D_entries (pos_type al, pos_type bl) |
void | fill_D_entries_noLP (pos_type al, pos_type bl) |
infty_score_t & | D (const ArcMatch &am) |
infty_score_t & | D (const Arc &arcA, const Arc &arcB) |
template<class ScoringView > | |
void | trace (ScoringView sv) |
Public Attributes | |
const AlignerParams * | params_ |
the parameter for the alignment | |
const Scoring * | scoring_ |
the scores | |
Scoring * | mod_scoring_ |
const Sequence & | seqA_ |
sequence A | |
const Sequence & | seqB_ |
sequence B | |
const ArcMatches & | arc_matches_ |
the potential arc matches between A and B | |
const BasePairs & | bpsA_ |
base pairs of A | |
const BasePairs & | bpsB_ |
base pairs of B | |
AlignerRestriction | r_ |
restriction of alignment for k-best | |
ScoreMatrix | Dmat_ |
matrix indexed by the arc indices of rnas A and B | |
std::vector< M_matrix_t > | Ms_ |
std::vector< ScoreVector > | Es_ |
std::vector< infty_score_t > | Fs_ |
int | min_i_ |
subsequence of A left end, computed by trace back | |
int | min_j_ |
subsequence of B left end, computed by trace back | |
int | max_i_ |
subsequence of A right end, computed by align_top_level | |
int | max_j_ |
subsequence of B right end, computed by align_top_level | |
bool | D_created_ |
flag, is D already created? | |
Alignment | alignment_ |
resulting alignment | |
const UnmodifiedScoringView | def_scoring_view_ |
Default scoring view. | |
ModifiedScoringView | mod_scoring_view_ |
FreeEndgapsDescription | free_endgaps_ |
Implementation of Aligner.
type of matrix M
anonymous enum |
different states for computation of structure-local alignment.
LocARNA::AlignerImpl::AlignerImpl | ( | const AlignerImpl & | a | ) |
copy constructor
a | Aligner implementation |
LocARNA::AlignerImpl::AlignerImpl | ( | const Sequence & | seqA, |
const Sequence & | seqB, | ||
const ArcMatches & | arc_matches, | ||
const AlignerParams * | ap, | ||
const Scoring * | s | ||
) |
Construct from parameters.
seqA | sequence A |
seqB | sequence B |
arc_matches | arc matches |
ap | parameter for aligner |
s | scoring object |
Destructor
void LocARNA::AlignerImpl::align_D | ( | ) |
create the entries in the D matrix This function is called by align() (unless D_created)
void LocARNA::AlignerImpl::align_in_arcmatch | ( | pos_type | al, |
pos_type | ar, | ||
pos_type | bl, | ||
pos_type | br, | ||
bool | allow_exclusion | ||
) |
align the loops closed by arcs (al,ar) and (bl,br). in structure local alignment, this allows to introduce exclusions
al | left end of arc a |
ar | right end of arc a |
bl | left end of arc b |
br | right end of arc b |
allow_exclusion | whether to allow exclusions |
infty_score_t LocARNA::AlignerImpl::align_noex | ( | int | state, |
pos_type | al, | ||
pos_type | bl, | ||
pos_type | i, | ||
pos_type | j, | ||
ScoringView | sv | ||
) |
standard cases for alignment (without exlusion handling).
recursion cases that handle everything but exclusions (in the LSSA-paper this function was called NoEx
state | necessary for structure local, there state refers to a set of matrices M,E,F |
al | position in sequence A: left end of current arc match |
bl | position in sequence B: left end of current arc match |
i | position in sequence A, for which score is computed |
j | position in sequence B, for which score is computed |
sv | the scoring view to be used |
align the top-level with potential free end gaps and return the maximal score
infty_score_t LocARNA::AlignerImpl::align_top_level_locally | ( | ScoringView | sv | ) |
align the top-level in a sequence local alignment and return the maximal score
infty_score_t& LocARNA::AlignerImpl::D | ( | const ArcMatch & | am | ) | [inline] |
Read/Write access to D matrix
am | Arc match |
infty_score_t& LocARNA::AlignerImpl::D | ( | const Arc & | arcA, |
const Arc & | arcB | ||
) | [inline] |
Read/Write access to D matrix
arcA | arc in sequence A |
arcB | arc in sequence B |
void LocARNA::AlignerImpl::fill_D_entries | ( | pos_type | al, |
pos_type | bl | ||
) |
fill in D the entries with left ends al,bl
void LocARNA::AlignerImpl::fill_D_entries_noLP | ( | pos_type | al, |
pos_type | bl | ||
) |
fill D entries when no-lonely-pairs option given after computation of M-matrices with left ends al,bl
this fills D entries for arc matches with left ends al-1,bl-1, since the positions refer to the inner arc of a stacked arc pair
void LocARNA::AlignerImpl::init_state | ( | int | state, |
pos_type | al, | ||
pos_type | ar, | ||
pos_type | bl, | ||
pos_type | br, | ||
bool | globalA, | ||
bool | exclA, | ||
bool | globalB, | ||
bool | exclB, | ||
ScoringView | sv | ||
) |
initialize matrices M and E
initialize first column and row of matrices M and E for the alignment below of arc match (a,b). The initialization depends on the state. First row/column means the row al and column bl. For correct initialization (in particular in local modes), globalA/B and exclA/B need to be given correctly for the state!
state | the state, selects the matrices M,E |
al | left end of arc a |
ar | right end of arc a |
bl | left end of arc b |
br | right end of arc b |
globalA | allow no free deletion of prefix of sequence A |
exclA | allow deletion of prefix of sequence A with cost exclusion() |
globalB | analogous for sequence B |
exclB | analogous for sequence B |
sv | Scoring view |
void LocARNA::AlignerImpl::trace | ( | ScoringView | sv | ) |
do the trace back through the alignment matrix with partial recomputation pre: call align() to fill the top-level matrix
void LocARNA::AlignerImpl::trace_arcmatch | ( | const ArcMatch & | am | ) |
trace an arc match
am | the arc match |
void LocARNA::AlignerImpl::trace_arcmatch_noLP | ( | const ArcMatch & | am | ) |
trace an arc match in case of forbidden lonely pairs
am | the arc match |
void LocARNA::AlignerImpl::trace_in_arcmatch | ( | int | state, |
int | al, | ||
int | i, | ||
int | bl, | ||
int | j, | ||
bool | top_level, | ||
ScoringView | sv | ||
) |
align top level in the scanning version
trace back within an match of arcs
state | the state selects M/E/F matrices (used in structure local alig) |
al | left end of arc in A |
i | right end of subsequence in A |
bl | left end of arc in B |
j | right end of subsequence in B |
top_level | whether alignment is on top level |
sv | scoring view |
void LocARNA::AlignerImpl::trace_noex | ( | int | state, |
pos_type | al, | ||
pos_type | i, | ||
pos_type | bl, | ||
pos_type | j, | ||
bool | top_level, | ||
ScoringView | sv | ||
) |
standard cases in trace back (without handling of exclusions)
state | the state selects M/E/F matrices (used in structure local alig) |
al | left end of arc in A |
i | right end of subsequence in A |
bl | left end of arc in B |
j | right end of subsequence in B |
top_level | whether alignment is on top level |
sv | scoring view |
std::vector<ScoreVector> LocARNA::AlignerImpl::Es_ |
for cool affine gap cost, we need two additional matrices E and F. However we only need to store one row for E and one scalar for F.
std::vector<infty_score_t> LocARNA::AlignerImpl::Fs_ |
for affine gap cost.
used in normalized scoring, when we need to modify the scoring
Modified scoring view for normalized alignment
std::vector<M_matrix_t> LocARNA::AlignerImpl::Ms_ |
M matrices
restriction of alignment for k-best
The AlignerRestriction r is used for the k-best local alignments.
Aligner always works on sub-sequences/structures of seqA and seqB. These are specified by r.
In the standard case, i.e. align the whole sequences, the values are set to startA=1 and endA=seqA.length() and analogously for B
The constructor initializes to the above standard values methods provide possibility to restriction.