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_

Detailed Description

Implementation of Aligner.

Member Typedef Documentation

typedef ScoreMatrix LocARNA::AlignerImpl::M_matrix_t

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

LocARNA::AlignerImpl::AlignerImpl ( const AlignerImpl & a )

copy constructor

Parameters:

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.

Parameters:

seqA	sequence A
seqB	sequence B
arc_matches	arc matches
ap	parameter for aligner
s	scoring object

LocARNA::AlignerImpl::~AlignerImpl ( )

Destructor

Member Function Documentation

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

Parameters:

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

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:

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

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

infty_score_t LocARNA::AlignerImpl::align_top_level_free_endgaps ( )

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:

am Arc 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:

arcA	arc in sequence A
arcB	arc 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:

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

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

void LocARNA::AlignerImpl::trace_arcmatch ( const ArcMatch & am )

trace an arc match

Parameters:

am	the arc match

void LocARNA::AlignerImpl::trace_arcmatch_noLP ( const ArcMatch & am )

trace an arc match in case of forbidden lonely pairs

Parameters:

am	the 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:

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

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:

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