LocARNA-1.9.2
 All Classes Files Functions Variables Typedefs Enumerations Enumerator Friends
Classes | Public Types | Public Member Functions | Public Attributes
LocARNA::AlignerImpl Class Reference

Implementation of Aligner. More...

#include <aligner_impl.hh>

List of all members.

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_tD (const ArcMatch &am)
infty_score_tD (const Arc &arcA, const Arc &arcB)
template<class ScoringView >
void trace (ScoringView sv)

Public Attributes

const AlignerParamsparams_
 the parameter for the alignment
const Scoringscoring_
 the scores
Scoringmod_scoring_
const SequenceseqA_
 sequence A
const SequenceseqB_
 sequence B
const ArcMatchesarc_matches_
 the potential arc matches between A and B
const BasePairsbpsA_
 base pairs of A
const BasePairsbpsB_
 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_tMs_
std::vector< ScoreVector > Es_
std::vector< infty_score_tFs_
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_

Detailed Description

Implementation of Aligner.


Member Typedef Documentation

type of matrix M

Note:
'typedef RMtrix<infty_score_t> M_matrix_t;' didn't improve performance

Member Enumeration Documentation

anonymous enum

different states for computation of structure-local alignment.

Note:
The idea of the names is E=exclusion, NO=no exclusion, X=one exclusion, OP=open exclusion. In E_1_2, 1 refers to sequence A and 2 to sequence B.

Constructor & Destructor Documentation

copy constructor

Parameters:
aAligner implementation
LocARNA::AlignerImpl::AlignerImpl ( const Sequence seqA,
const Sequence seqB,
const ArcMatches arc_matches,
const AlignerParams ap,
const Scoring s 
)

Construct from parameters.

Parameters:
seqAsequence A
seqBsequence B
arc_matchesarc matches
apparameter for aligner
sscoring object

Destructor


Member Function Documentation

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

Parameters:
alleft end of arc a
arright end of arc a
blleft end of arc b
brright end of arc b
allow_exclusionwhether to allow exclusions
Precondition:
arc-match (al,ar)~(bl,br) valid due to constraints and heuristics
template<class ScoringView >
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

Parameters:
statenecessary for structure local, there state refers to a set of matrices M,E,F
alposition in sequence A: left end of current arc match
blposition in sequence B: left end of current arc match
iposition in sequence A, for which score is computed
jposition in sequence B, for which score is computed
svthe scoring view to be used
Returns:
score of i,j in matrix set state that results from standard cases
Precondition:
state in 0..4, in non-structure local alignment state has to be 0;
i,j is allowed by edge controller

align the top-level with potential free end gaps and return the maximal score

template<class ScoringView >
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

Parameters:
amArc match
Returns:
entry of D matrix for am
infty_score_t& LocARNA::AlignerImpl::D ( const Arc arcA,
const Arc arcB 
) [inline]

Read/Write access to D matrix

Parameters:
arcAarc in sequence A
arcBarc in sequence B
Returns:
entry of D matrix for match of arcA and arcB
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

template<class ScoringView >
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!

Parameters:
statethe state, selects the matrices M,E
alleft end of arc a
arright end of arc a
blleft end of arc b
brright end of arc b
globalAallow no free deletion of prefix of sequence A
exclAallow deletion of prefix of sequence A with cost exclusion()
globalBanalogous for sequence B
exclBanalogous for sequence B
svScoring view
template<class ScoringView >
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

trace an arc match

Parameters:
amthe arc match

trace an arc match in case of forbidden lonely pairs

Parameters:
amthe arc match
template<class ScoringView >
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

Parameters:
statethe state selects M/E/F matrices (used in structure local alig)
alleft end of arc in A
iright end of subsequence in A
blleft end of arc in B
jright end of subsequence in B
top_levelwhether alignment is on top level
svscoring view
template<class ScoringView >
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)

Parameters:
statethe state selects M/E/F matrices (used in structure local alig)
alleft end of arc in A
iright end of subsequence in A
blleft end of arc in B
jright end of subsequence in B
top_levelwhether alignment is on top level
svscoring view

Member Data Documentation

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.

Note:
for structure local, we need one such matrix per state 0..3
See also:
Fs

for affine gap cost.

See also:
Es

used in normalized scoring, when we need to modify the scoring

Modified scoring view for normalized alignment

M matrices

Note:
in the case of structure local alignment, the algo uses eight 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.


The documentation for this class was generated from the following files:
 All Classes Files Functions Variables Typedefs Enumerations Enumerator Friends