LocARNA::AlignerN Class Reference

Implements SPARSE, next generation alignment algorithm for locarna. More...

#include <aligner_n.hh>

List of all members.

Classes
class	ModifiedScoringViewN
	Provides a modified view on the scoring. More...
class	UnmodifiedScoringViewN
	Provides the standard view on the scoring. More...
Public Types
typedef BasePairs__Arc	Arc
	type for an arc a.k.a base pair
typedef SparsificationMapper::ArcIdx	ArcIdx
	type for arc index
typedef SparsificationMapper::ArcIdxVec	ArcIdxVec
	vector of arc indices
typedef SparsificationMapper::matidx_t	matidx_t
	type for a matrix position
typedef SparsificationMapper::seq_pos_t	seq_pos_t
	type for a sequence position
typedef SparsificationMapper::index_t	index_t
	type for an index
typedef ScoreMatrix	M_matrix_t
	type of matrix M
Public Member Functions
	AlignerN (const AlignerN &a)
	copy constructor
	AlignerN (const AlignerParams &ap)
	Construct from parameters.
	~AlignerN ()
	destructor
Alignment const &	get_alignment () const
	return the alignment that was computed by trace()
infty_score_t	align ()
	compute the alignment score
void	trace ()
	offer trace as public method. Calls trace(def_scoring_view).
Static Public Member Functions
static AlignerNParams	create ()
	create with named parameters
Protected Member Functions
template<class ScoringView >
void	init_M_E_F (pos_type al, pos_type ar, pos_type bl, pos_type br, ScoringView sv)
	initialize matrices M
template<bool isA, class ScoringView >
void	initGapCostMat (ScoringView sv)
	compute and stores score of aligning subsequences to gaps
template<bool isA>
infty_score_t	getGapCostBetween (pos_type leftSide, pos_type rightSide)
	return score of aligning a subsequence to gaps
template<bool isA, class ScoringView >
infty_score_t	compute_IX (pos_type xl, const Arc &arcY, pos_type i, ScoringView sv)
	compute IA/IB value of single element
void	fill_IA_entries (pos_type al, Arc arcB, pos_type max_ar)
	fills all IA values using default scoring scheme
void	fill_IB_entries (Arc arcA, pos_type bl, pos_type max_br)
	fills all IB values using default scoring scheme
template<class ScoringView >
infty_score_t	compute_E_entry (index_t al, matidx_t i_index, matidx_t j_index, seq_pos_t i_seq_pos, seq_pos_t i_prev_seq_pos, ScoringView sv)
	compute E matrix value of single matrix element
template<class ScoringView >
infty_score_t	compute_F_entry (index_t bl, matidx_t i_index, matidx_t j_index, seq_pos_t i_seq_pos, seq_pos_t i_prev_seq_pos, ScoringView sv)
	compute F matrix value of single matrix element
template<class ScoringView >
infty_score_t	compute_M_entry (index_t al, index_t bl, matidx_t index_i, matidx_t index_j, ScoringView sv)
	compute M value of single matrix element
void	fill_M_entries (pos_type al, pos_type ar, pos_type bl, pos_type br)
template<class ScoringView >
void	trace_E (pos_type al, matidx_t i_index, pos_type bl, matidx_t j_index, bool top_level, ScoringView sv)
	trace back base deletion within a match of arcs
template<class ScoringView >
void	trace_F (pos_type al, matidx_t i_index, pos_type bl, matidx_t j_index, bool top_level, ScoringView sv)
	trace back base insertion within a match of arcs
template<class ScoringView >
void	trace_M (pos_type al, matidx_t i_index, pos_type bl, matidx_t j_index, bool tl, ScoringView sv)
	trace back within an arc match
template<class ScoringView >
void	trace_M_noex (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)
template<bool isA, class ScoringView >
void	trace_IXD (const Arc &arcA, const Arc &arcB, ScoringView sv)
template<class ScoringView >
void	trace_D (const Arc &arcA, const Arc &arcB, ScoringView sv)
template<bool isA, class ScoringView >
void	trace_IX (pos_type xl, pos_type i, const Arc &arcY, ScoringView sv)
void	align_D ()
void	fill_D_entries (pos_type al, pos_type bl)
infty_score_t &	D (const ArcMatch &am)
template<bool isA>
infty_score_t &	D (const Arc &arcX, const Arc &arcY)
infty_score_t &	D (const Arc &arcA, const Arc &arcB)
template<bool isA>
infty_score_t &	IX (const pos_type i, const Arc &arc)
template<bool isA>
infty_score_t &	IXD (const Arc &arc1, const Arc &arc2)
infty_score_t &	IA (const pos_type i, const Arc &b)
infty_score_t &	IB (const Arc &a, const pos_type k)
template<class ScoringView >
void	trace (ScoringView sv)
Protected Attributes
const AlignerNParams *	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 SparsificationMapper &	mapperA
	sparsification mapping for seq A
const SparsificationMapper &	mapperB
	sparsification mapping for seq 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 AlignerN
ScoreMatrix	Dmat
	matrix indexed by the arc indices of rnas A and B
ScoreMatrix	IAmat
ScoreMatrix	IBmat
ScoreMatrix	IADmat
ScoreMatrix	IBDmat
ScoreMatrix	Emat
	matrix for the affine gap cost model base deletion
ScoreMatrix	Fmat
	matrix for the affine gap cost model base insertion
M_matrix_t	M
	M matrix.
ScoreMatrix	gapCostMatA
ScoreMatrix	gapCostMatB
int	min_i
	subsequence of A left end, not used in sparse
int	min_j
	subsequence of B left end, not used in sparse
int	max_i
	subsequence of A right end, not used in sparse
int	max_j
	subsequence of B right end, not used in sparse
bool	D_created
	flag, is D already created?
Alignment	alignment
	resulting alignment
const UnmodifiedScoringViewN	def_scoring_view
	Default scoring view.
ModifiedScoringViewN	mod_scoring_view

---

Detailed Description

Implements SPARSE, next generation alignment algorithm for locarna.

Performs the alignment of two sequences and their associated sets of weighted basepairs

An object always knows about the two sequences and the two weighted base pair sets

usage: construct, align, trace, get_alignment

Todo:

implement noLP in sparse algorithm

---

Constructor & Destructor Documentation

LocARNA::AlignerN::AlignerN

(

const AlignerParams &

ap

)

Construct from parameters.

Parameters:

ap	parameter for aligner

Note:

ap is copied to allow reference to a temporary

for implicit type cast

---

Member Function Documentation

void LocARNA::AlignerN::align_D

(

)

[protected]

create the entries in the D matrix This function is called by align() (unless D_created)

template<class ScoringView >

infty_score_t LocARNA::AlignerN::compute_E_entry	(	index_t	al,
		matidx_t	i_index,
		matidx_t	j_index,
		seq_pos_t	i_seq_pos,
		seq_pos_t	i_prev_seq_pos,
		ScoringView	sv
	)		[protected]

compute E matrix value of single matrix element

Parameters:

al
i_index	position in sequence A:
j_index	position in sequence B:
i_seq_pos	position in sequence A, for which score is computed
i_prev_seq_pos	position in sequence A, first valid seq position before i_index
sv	the scoring view to be used

Returns:

score of E(i,j)

template<class ScoringView >

infty_score_t LocARNA::AlignerN::compute_F_entry	(	index_t	bl,
		matidx_t	i_index,
		matidx_t	j_index,
		seq_pos_t	i_seq_pos,
		seq_pos_t	i_prev_seq_pos,
		ScoringView	sv
	)		[protected]

compute F matrix value of single matrix element

Parameters:

bl
i_index	position in sequence A:
j_index	position in sequence B:
j_seq_pos	position in sequence B, for which score is computed
j_prev_seq_pos	position in sequence B, first valid seq position before i_index
sv	the scoring view to be used

Returns:

score of E(i,j)

template<bool isA, class ScoringView >

infty_score_t LocARNA::AlignerN::compute_IX	(	pos_type	xl,
		const Arc &	arcY,
		pos_type	i,
		ScoringView	sv
	)		[protected]

compute IA/IB value of single element

Parameters:

isA	switch to determine IX is IA/IB
xl	position in sequence A/B: left end of current arc match
arcY	arc in sequence B/A, for which score is computed
i	position in sequence A/B, for which score is computed
sv	the scoring view to be used

Returns:

score of IX(i,arcX) for the left end arc element i

template<class ScoringView >

infty_score_t LocARNA::AlignerN::compute_M_entry	(	index_t	al,
		index_t	bl,
		matidx_t	index_i,
		matidx_t	index_j,
		ScoringView	sv
	)		[protected]

compute M value of single matrix element

Parameters:

al	position in sequence A: left end of current arc match
bl	position in sequence B: left end of current arc match
index_i	index position in sequence A, for which score is computed
index_j	index position in sequence B, for which score is computed
sv	the scoring view to be used

Returns:

score of M(i,j) for the arcs left ended by al, bl

static AlignerNParams LocARNA::AlignerN::create

(

)

[inline, static]

create with named parameters

Returns:

parameter object

infty_score_t& LocARNA::AlignerN::D

(

const ArcMatch &

am

)

[inline, protected]

Read/Write access to D matrix

Parameters:

am

Arc match

Returns:

entry of D matrix for am

template<bool isA>

infty_score_t& LocARNA::AlignerN::D	(	const Arc &	arcX,
		const Arc &	arcY
	)		[inline, protected]

Read/Write access to D matrix

Parameters:

arcX	arc in A/B determined by isA
arcY	arc in B/A determined by isA
isA	swap arcX/Y parameters

Returns:

D matrix entry for match of arcX<->arcY

infty_score_t& LocARNA::AlignerN::D	(	const Arc &	arcA,
		const Arc &	arcB
	)		[inline, protected]

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::AlignerN::fill_D_entries	(	pos_type	al,
		pos_type	bl
	)		[protected]

fill in D the entries with left ends al,bl

Parameters:

al	position in sequence A: left end of current arc match
bl	position in sequence A: left end of current arc match

void LocARNA::AlignerN::fill_IA_entries	(	pos_type	al,
		Arc	arcB,
		pos_type	max_ar
	)		[protected]

fills all IA values using default scoring scheme

Parameters:

al	position in sequence A: left end of current arc match
arcB	arc in sequence B, for which score is computed
max_ar	rightmost possible for an arc starting with the left end al in sequence A: maximum right end of current arc match

void LocARNA::AlignerN::fill_IB_entries	(	Arc	arcA,
		pos_type	bl,
		pos_type	max_br
	)		[protected]

fills all IB values using default scoring scheme

Parameters:

arcA	arc in sequence A, for which score is computed
bl	position in sequence B: left end of current arc match
max_br	rightmost possible for an arc with the left end of bl in sequence B: maximum right end of current arc match

void LocARNA::AlignerN::fill_M_entries	(	pos_type	al,
		pos_type	ar,
		pos_type	bl,
		pos_type	br
	)		[protected]

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, not supported by sparse

Precondition:

arc-match (al,ar)~(bl,br) valid due to constraints and heuristics

template<bool isA>

infty_score_t LocARNA::AlignerN::getGapCostBetween	(	pos_type	leftSide,
		pos_type	rightSide
	)		[inline, protected]

return score of aligning a subsequence to gaps

Parameters:

leftSide	sequence position before left side of the subsequence
rightSide	sequence position after right side of the subsequence
isA	a switch to determine the target sequence A or B

infty_score_t& LocARNA::AlignerN::IA	(	const pos_type	i,
		const Arc &	b
	)		[inline, protected]

Read/Write access to IA matrix

Parameters:

i	rightside position in seqA
b	arc in B

Returns:

IA matrix entry for position i of a and arc b

infty_score_t& LocARNA::AlignerN::IB	(	const Arc &	a,
		const pos_type	k
	)		[inline, protected]

Read/Write access to IB matrix

Parameters:

a	arc in A
k	rightside position in seqB

Returns:

IB matrix entry for arc a and position k in b

template<class ScoringView >

void LocARNA::AlignerN::init_M_E_F	(	pos_type	al,
		pos_type	ar,
		pos_type	bl,
		pos_type	br,
		ScoringView	sv
	)		[protected]

initialize matrices M

initialize first column and row of matrices M for the alignment below of arc match (a,b). First row/column means the row al and column bl.

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
sv	Scoring view

template<bool isA, class ScoringView >

void LocARNA::AlignerN::initGapCostMat

(

ScoringView

sv

)

[protected]

compute and stores score of aligning subsequences to gaps

Parameters:

isA	a switch to determine the target sequence A or B
sv	the scoring view to be used

Returns:

writes gap costs into gapCost{A,B}mat (depending on isA)

template<bool isA>

infty_score_t& LocARNA::AlignerN::IX	(	const pos_type	i,
		const Arc &	arc
	)		[inline, protected]

Read/Write access to IAorIB matrix

Parameters:

i	rightside position in seqA/B
arc	arc in A/B
isA	switch to determine IA/IB

Returns:

IA/IB matrix entry for position k and arc

template<bool isA>

infty_score_t& LocARNA::AlignerN::IXD	(	const Arc &	arc1,
		const Arc &	arc2
	)		[inline, protected]

Read/Write access to IAD orIBD matrix

Parameters:

i	rightside position in seqA/B
arac	arc in A/B
isA	switch to determine IA/IB

Returns:

IA/IB matrix entry for position k and arc

template<class ScoringView >

void LocARNA::AlignerN::trace

(

ScoringView

sv

)

[protected]

do the trace back through the alignment matrix with partial recomputation pre: call align() to fill the top-level matrix

template<class ScoringView >

void LocARNA::AlignerN::trace_D	(	const Arc &	arcA,
		const Arc &	arcB,
		ScoringView	sv
	)		[protected]

trace D matrix

Parameters:

arcA	the corresponding arc in A which defines the D element
arcB	the corresponding arc in B which defines the D element
sv	scoring view

template<class ScoringView >

void LocARNA::AlignerN::trace_E	(	pos_type	al,
		matidx_t	i_index,
		pos_type	bl,
		matidx_t	j_index,
		bool	top_level,
		ScoringView	sv
	)		[protected]

trace back base deletion within a match of arcs

Parameters:

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::AlignerN::trace_F	(	pos_type	al,
		matidx_t	i_index,
		pos_type	bl,
		matidx_t	j_index,
		bool	top_level,
		ScoringView	sv
	)		[protected]

trace back base insertion within a match of arcs

Parameters:

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<bool isA, class ScoringView >

void LocARNA::AlignerN::trace_IX	(	pos_type	xl,
		pos_type	i,
		const Arc &	arcY,
		ScoringView	sv
	)		[protected]

trace D matrix

Parameters:

am	the corresponding arcs which defines the D element
sv	scoring view trace IA/IB matrix
xl	position in sequence A/B: left end of current arc match
i	position in sequence A/B, for which score is computed
arcY	arc in sequence B/A, for which score is computed
isA	switch to determine IA/IB
sv	the scoring view to be used

template<bool isA, class ScoringView >

void LocARNA::AlignerN::trace_IXD	(	const Arc &	arcA,
		const Arc &	arcB,
		ScoringView	sv
	)		[protected]

trace IAD IBD matrix

Parameters:

arcA	the corresponding arc in A which defines the IAD/IBD element
arcB	the corresponding arc in B which defines the IAD/IBD element
sv	scoring view

template<class ScoringView >

void LocARNA::AlignerN::trace_M	(	pos_type	al,
		matidx_t	i_index,
		pos_type	bl,
		matidx_t	j_index,
		bool	tl,
		ScoringView	sv
	)		[protected]

trace back within an arc match

Parameters:

al	left end of arc in A
i_index	index for right end of subsequence in A
bl	index for left end of arc in B
j_index	right end of subsequence in B
tl	whether alignment is on top level
sv	scoring view

template<class ScoringView >

void LocARNA::AlignerN::trace_M_noex	(	pos_type	al,
		pos_type	i,
		pos_type	bl,
		pos_type	j,
		bool	top_level,
		ScoringView	sv
	)		[protected]

standard cases in trace back (without handling of exclusions)

Parameters:

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

---

Member Data Documentation

ScoreMatrix LocARNA::AlignerN::gapCostMatA [protected]

matrix to store cost of deleting/inserting a subsequence of sequence A, indexed by neighboring positions of the range; the cost does not take into account whether the gap is compatible with constraints

ScoreMatrix LocARNA::AlignerN::gapCostMatB [protected]

matrix to store cost of deleting/inserting a subsequence of sequence B, indexed by neighboring positions of the range; the cost does not take into account whether the gap is compatible with constraints

ScoreMatrix LocARNA::AlignerN::IADmat [protected]

matrix indexed by positions of elements of the seqA positions and the arc indices of RNA B

ScoreMatrix LocARNA::AlignerN::IAmat [protected]

matrix indexed by positions of elements of the seqA positions and the arc indices of RNA B

ScoreMatrix LocARNA::AlignerN::IBDmat [protected]

matrix indexed by positions of elements of the seqB positions and the arc indices of RNA A

ScoreMatrix LocARNA::AlignerN::IBmat [protected]

matrix indexed by positions of elements of the seqB positions and the arc indices of RNA A

M_matrix_t LocARNA::AlignerN::M [protected]

M matrix.

use only one M matrix (unlike in Aligner), since we don't handle structure locality

Scoring* LocARNA::AlignerN::mod_scoring [protected]

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

ModifiedScoringViewN LocARNA::AlignerN::mod_scoring_view [protected]

Modified scoring view for normalized alignment

---

The documentation for this class was generated from the following files:

• src/LocARNA/aligner_n.hh
• src/LocARNA/aligner_n.cc