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

#include <aligner_n.hh>

Collaboration diagram for LocARNA::AlignerN:

[legend]

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. More...

	~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 More...

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 More...

template<class ScoringView >
void	computeGapCosts (bool isA, ScoringView sv)
	compute and stores score of aligning subsequences to the gap More...

infty_score_t	getGapCostBetween (pos_type leftSide, pos_type rightSide, bool isA)
	return score of aligning a subsequence to the gap More...

template<class ScoringView >
infty_score_t	compute_IX (pos_type xl, const Arc &arcY, pos_type i, bool isA, ScoringView sv)
	compute IA/IB value of single element More...

void	fill_IA_entries (pos_type al, Arc arcB, pos_type max_ar)
	fills all IA values using default scoring scheme More...

void	fill_IB_entries (Arc arcA, pos_type bl, pos_type max_br)
	fills all IB values using default scoring scheme More...

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 More...

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 More...

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 More...

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 More...

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 More...

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 More...

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) More...

template<class ScoringView >
void	trace_IXD (const Arc &arcA, const Arc &arcB, bool isA, ScoringView sv)

template<class ScoringView >
void	trace_D (const Arc &arcA, const Arc &arcB, ScoringView sv)

template<class ScoringView >
void	trace_IX (pos_type xl, pos_type i, const Arc &arcY, bool isA, ScoringView sv)

void	align_D ()

void	fill_D_entries (pos_type al, pos_type bl)

infty_score_t &	D (const ArcMatch &am)

infty_score_t &	D (const Arc &arcX, const Arc &arcY, bool isA)

infty_score_t &	D (const Arc &arcA, const Arc &arcB)

infty_score_t &	IX (const pos_type i, const Arc &arc, bool isA)

infty_score_t &	IXD (const Arc &arc1, const Arc &arc2, bool isA)

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
	used in normalized scoring, when we need to modify the 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
	matrix indexed by positions of elements of the seqA positions and the arc indices of RNA B

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

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

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

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. More...

ScoreMatrix	gapCostAmat

ScoreMatrix	gapCostBmat

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
	Modified scoring view for normalized alignment.

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

infty_score_t LocARNA::AlignerN::compute_IX	(	pos_type	xl,
		const Arc &	arcY,
		pos_type	i,
		bool	isA,
		ScoringView	sv
	)

protected

compute IA/IB value of single element

Parameters

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
isA	switch to determine IX is IA/IB
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

template<class ScoringView >

void LocARNA::AlignerN::computeGapCosts	(	bool	isA,
		ScoringView	sv
	)

protected

compute and stores score of aligning subsequences to the gap

Parameters

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

static AlignerNParams LocARNA::AlignerN::create ( )

inlinestatic

create with named parameters

Returns: parameter object

infty_score_t& LocARNA::AlignerN::D ( const ArcMatch & am )

inlineprotected

Read/Write access to D matrix

Parameters

am Arc match

Returns: entry of D matrix for am

infty_score_t& LocARNA::AlignerN::D	(	const Arc &	arcX,
		const Arc &	arcY,
		bool	isA
	)

inlineprotected

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
	)

inlineprotected

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

infty_score_t LocARNA::AlignerN::getGapCostBetween	(	pos_type	leftSide,
		pos_type	rightSide,
		bool	isA
	)

inlineprotected

return score of aligning a subsequence to the gap

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
	)

inlineprotected

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
	)

inlineprotected

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

infty_score_t& LocARNA::AlignerN::IX	(	const pos_type	i,
		const Arc &	arc,
		bool	isA
	)

inlineprotected

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

infty_score_t& LocARNA::AlignerN::IXD	(	const Arc &	arc1,
		const Arc &	arc2,
		bool	isA
	)

inlineprotected

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

void LocARNA::AlignerN::trace_IX	(	pos_type	xl,
		pos_type	i,
		const Arc &	arcY,
		bool	isA,
		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<class ScoringView >

void LocARNA::AlignerN::trace_IXD	(	const Arc &	arcA,
		const Arc &	arcB,
		bool	isA,
		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::gapCostAmat

protected

matrix to store cost of deleting/inserting a subsequence of sequence A, indexed by neighboring positions of the range

ScoreMatrix LocARNA::AlignerN::gapCostBmat

protected

matrix to store cost of deleting/inserting a subsequence of sequence B, indexed by neighboring positions of the range

M_matrix_t LocARNA::AlignerN::M

protected

M matrix.

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

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

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

Classes

Public Types

Public Member Functions

Static Public Member Functions

Protected Member Functions

Protected Attributes

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation