BTL - Algorithms

Algorithms and Function Objects

Algorithms

Included in the library are one, two, and three dimensional fast Fourier transform methods, a method for inverting symmetric matrices based on Cholesky factorisation, and a least squares coordinate superposition method that uses the method of Kearsley (Kearsley, 1989).

Algorithm	Description	Requirements of Containers	Performance
FFT	1,2,and 3 dimensional fast Fourier transform	1. random access iterator 2. sequential storage of elements in a particular order	1D O(nlog n) 2D O([nlog n]2) 3D O([nlog n]3)
Least SquaresFit	Fit one set of three dimensional co-ordinates to another	1. forward iterator 2. sequential storage in a particular order	O(n)
Cholesky Inverse	Calculate the inverse of symmetric matrix	1. size_type and value_type defining the types matrix subscripts and contents used 2. NumOfCols() and NumOfRows() functions to obtain the dimensions of the matrix 3. a () operator for direct access to matrix elements via subscripts . Subscripts should start at 1 and be in row, column pairs	O(n3)

Function Object

There are two function objects, or functors, in the BTL, PDBSort and AminoAcidProperty. PDBSort can be used as parameter for the STL generic sort algorithms. This functor takes 2 input strings containing atom names and returns true if the first name comes before the second in order found in Brookhaven pdb format files (Bernstein et al., 1977) and false if doesn't. The atom names and the order were extracted from Roger Sayle's mdl2pdb program (personal communication). AminoAcidProperty takes a single character as input and returns a real number property value for the amino acid the character represents. The type of property produced is defined when the function object is constructed. Properties currently supported are volume, surface area, and several hydropathy scales. One use of this functor is to take an amino acid sequence stored in one container and create from it a second container of property values using the STL generic function transform.