Library functions for dynamic programming. More...

#include "dynamic_programming.h"
#include "utilities.h"

Functions
long	dp_matrix_scoring (Matrix mat, double gapopen, double gapextend)
	Calculates the scoring matrix in dynamic programming. More...

int *	dp_matrix_backtrace (Matrix mat, double gapopen, double gapextend, long &length)
	Backtraces the scoring matrix in dynamic programming. More...

Variables
int	verbose

Detailed Description

Library functions for dynamic programming.

Author: Bernard Heymann

Date: Created: 20050622; Modified: 20110810

Function Documentation

◆ dp_matrix_backtrace()

int * dp_matrix_backtrace	(	Matrix	mat,
		double	gapopen,
		double	gapextend,
		long &	length
	)

Backtraces the scoring matrix in dynamic programming.

Parameters

mat	matrix.
gapopen	gap opening penalty.
gapextend	gap extension penalty.
*length	length of alignment.

Returns

int* alignment array with indices.

Implementation of the Needleman-Wunsch algorithm.
The scoring matrix for dynamic programming is backtraced into an integer 
array holding the indices from the corresponding sequences, or -1 for gaps. 
The array is double the length of the alignment and holds two sets of 
indices, the first in the first half and the second in last half.
The length of the alignment is returned in the pointer of the last argument.

◆ dp_matrix_scoring()

long dp_matrix_scoring	(	Matrix	mat,
		double	gapopen,
		double	gapextend
	)

Calculates the scoring matrix in dynamic programming.

Parameters

mat	matrix.
gapopen	gap opening penalty.
gapextend	gap extension penalty.

Returns

long index of the maximum in the matrix.

Implementation of the Needleman-Wunsch algorithm.
The input matrix can be any form of similarity or coincidence matrix, and
is modified by dynamic programming in preparation for backtracing.

Variable Documentation

◆ verbose

int verbose

extern