Implementations to solve various combinatorial aspects for strings of objects. More...

Detailed Description

Implementations to solve various combinatorial aspects for strings of objects.

Collaboration diagram for Combinatorics Algorithms:

Files
file	combinatorics.h
	Various implementations that deal with combinatorial aspects of objects.

Functions
unsigned int **	vrna_enumerate_necklaces (const unsigned int *type_counts)
	Enumerate all necklaces with fixed content. More...

unsigned int	vrna_rotational_symmetry_num (const unsigned int *string, size_t string_length)
	Determine the order of rotational symmetry for a string of objects represented by natural numbers. More...

unsigned int	vrna_rotational_symmetry_pos_num (const unsigned int string, size_t string_length, unsigned int *positions)
	Determine the order of rotational symmetry for a string of objects represented by natural numbers. More...

unsigned int	vrna_rotational_symmetry (const char *string)
	Determine the order of rotational symmetry for a NULL-terminated string of ASCII characters. More...

unsigned int	vrna_rotational_symmetry_pos (const char string, unsigned int *positions)
	Determine the order of rotational symmetry for a NULL-terminated string of ASCII characters. More...

unsigned int	vrna_rotational_symmetry_db (vrna_fold_compound_t fc, const char structure)
	Determine the order of rotational symmetry for a dot-bracket structure. More...

unsigned int	vrna_rotational_symmetry_db_pos (vrna_fold_compound_t fc, const char structure, unsigned int **positions)
	Determine the order of rotational symmetry for a dot-bracket structure. More...

Function Documentation

unsigned int ** vrna_enumerate_necklaces ( const unsigned int * type_counts )

#include <ViennaRNA/combinatorics.h>

Enumerate all necklaces with fixed content.

This function implements A fast algorithm to generate necklaces with fixed content as published by Joe Sawada in 2003 [19].

The function receives a list of counts (the elements on the necklace) for each type of object within a necklace. The list starts at index 0 and ends with an entry that has a count of 0. The algorithm then enumerates all non-cyclic permutations of the content, returned as a list of necklaces. This list, again, is zero-terminated, i.e. the last entry of the list is a NULL pointer.

Parameters

type_counts A 0-terminated list of entity counts

Returns: A list of all non-cyclic permutations of the entities

SWIG Wrapper Notes:: This function is available as global function enumerate_necklaces() which accepts lists input, an produces list of lists output.

unsigned int vrna_rotational_symmetry_num	(	const unsigned int *	string,
		size_t	string_length
	)

#include <ViennaRNA/combinatorics.h>

Determine the order of rotational symmetry for a string of objects represented by natural numbers.

The algorithm applies a fast search of the provided string within itself, assuming the end of the string wraps around to connect with it's start. For example, a string of the form 011011 has rotational symmetry of order 2

This is a simplified version of vrna_rotational_symmetry_pos_num() that may be useful if one is only interested in the degree of rotational symmetry but not the actual set of rotational symmetric strings.

See also: vrna_rotational_symmetry_pos_num(), vrna_rotationa_symmetry()

Parameters

string	The string of elements encoded as natural numbers
string_length	The length of the string

Returns: The order of rotational symmetry

SWIG Wrapper Notes:: This function is available as global function rotational_symmetry(). See vrna_rotational_symmetry_pos() for details. Note, that in the target language the length of the list string is always known a-priori, so the parameter string_length must be omitted.

unsigned int vrna_rotational_symmetry_pos_num	(	const unsigned int *	string,
		size_t	string_length,
		unsigned int **	positions
	)

#include <ViennaRNA/combinatorics.h>

Determine the order of rotational symmetry for a string of objects represented by natural numbers.

The algorithm applies a fast search of the provided string within itself, assuming the end of the string wraps around to connect with it's start. For example, a string of the form 011011 has rotational symmetry of order 2

If the argument positions is not NULL, the function stores an array of string start positions for rotational shifts that map the string back onto itself. This array has length of order of rotational symmetry, i.e. the number returned by this function. The first element positions[0] always contains a shift value of 0 representing the trivial rotation.

Note: Do not forget to release the memory occupied by positions after a successful execution of this function.

See also: vrna_rotational_symmetry_num(), vrna_rotational_symmetry(), vrna_rotational_symmetry_pos()

Parameters

string	The string of elements encoded as natural numbers
string_length	The length of the string
positions	A pointer to an (undefined) list of alternative string start positions that lead to an identity mapping (may be NULL)

Returns: The order of rotational symmetry

SWIG Wrapper Notes:: This function is available as global function rotational_symmetry(). See vrna_rotational_symmetry_pos() for details. Note, that in the target language the length of the list string is always known a-priori, so the parameter string_length must be omitted.

unsigned int vrna_rotational_symmetry ( const char * string )

#include <ViennaRNA/combinatorics.h>

Determine the order of rotational symmetry for a NULL-terminated string of ASCII characters.

The algorithm applies a fast search of the provided string within itself, assuming the end of the string wraps around to connect with it's start. For example, a string of the form AABAAB has rotational symmetry of order 2

This is a simplified version of vrna_rotational_symmetry_pos() that may be useful if one is only interested in the degree of rotational symmetry but not the actual set of rotational symmetric strings.

See also: vrna_rotational_symmetry_pos(), vrna_rotationa_symmetry_num()

Parameters

string A NULL-terminated string of characters

Returns: The order of rotational symmetry

SWIG Wrapper Notes:: This function is available as global function rotational_symmetry(). See vrna_rotational_symmetry_pos() for details.

unsigned int vrna_rotational_symmetry_pos	(	const char *	string,
		unsigned int **	positions
	)

#include <ViennaRNA/combinatorics.h>

Determine the order of rotational symmetry for a NULL-terminated string of ASCII characters.

The algorithm applies a fast search of the provided string within itself, assuming the end of the string wraps around to connect with it's start. For example, a string of the form AABAAB has rotational symmetry of order 2

If the argument positions is not NULL, the function stores an array of string start positions for rotational shifts that map the string back onto itself. This array has length of order of rotational symmetry, i.e. the number returned by this function. The first element positions[0] always contains a shift value of 0 representing the trivial rotation.

Note: Do not forget to release the memory occupied by positions after a successful execution of this function.

See also: vrna_rotational_symmetry(), vrna_rotational_symmetry_num(), vrna_rotational_symmetry_num_pos()

Parameters

string	A NULL-terminated string of characters
positions	A pointer to an (undefined) list of alternative string start positions that lead to an identity mapping (may be NULL)

Returns: The order of rotational symmetry

SWIG Wrapper Notes:: This function is available as overloaded global function rotational_symmetry(). It merges the functionalities of vrna_rotational_symmetry(), vrna_rotational_symmetry_pos(), vrna_rotational_symmetry_num(), and vrna_rotational_symmetry_pos_num(). In contrast to our C-implementation, this function doesn't return the order of rotational symmetry as a single value, but returns a list of cyclic permutation shifts that result in a rotationally symmetric string. The length of the list then determines the order of rotational symmetry.

unsigned int vrna_rotational_symmetry_db	(	vrna_fold_compound_t *	fc,
		const char *	structure
	)

#include <ViennaRNA/combinatorics.h>

Determine the order of rotational symmetry for a dot-bracket structure.

Given a (permutation of multiple) RNA strand(s) and a particular secondary structure in dot-bracket notation, compute the degree of rotational symmetry. In case there is only a single linear RNA strand, the structure always has degree 1, as there are no rotational symmetries due to the direction of the nucleic acid sequence and the fixed positions of 5' and 3' ends. However, for circular RNAs, rotational symmetries might arise if the sequence consists of a concatenation of $k$ identical subsequences.

This is a simplified version of vrna_rotational_symmetry_db_pos() that may be useful if one is only interested in the degree of rotational symmetry but not the actual set of rotational symmetric strings.

See also: vrna_rotational_symmetry_db_pos(), vrna_rotational_symmetry(), vrna_rotational_symmetry_num()

Parameters

fc	A fold_compound data structure containing the nucleic acid sequence(s), their order, and model settings
structure	The dot-bracket structure the degree of rotational symmetry is checked for

Returns: The degree of rotational symmetry of the structure (0 in case of any errors)

SWIG Wrapper Notes:: This function is attached as method rotational_symmetry_db() to objects of type fold_compound (i.e. vrna_fold_compound_t). See vrna_rotational_symmetry_db_pos() for details.

unsigned int vrna_rotational_symmetry_db_pos	(	vrna_fold_compound_t *	fc,
		const char *	structure,
		unsigned int **	positions
	)

#include <ViennaRNA/combinatorics.h>

Determine the order of rotational symmetry for a dot-bracket structure.

Given a (permutation of multiple) RNA strand(s) and a particular secondary structure in dot-bracket notation, compute the degree of rotational symmetry. In case there is only a single linear RNA strand, the structure always has degree 1, as there are no rotational symmetries due to the direction of the nucleic acid sequence and the fixed positions of 5' and 3' ends. However, for circular RNAs, rotational symmetries might arise if the sequence consists of a concatenation of $k$ identical subsequences.

If the argument positions is not NULL, the function stores an array of string start positions for rotational shifts that map the string back onto itself. This array has length of order of rotational symmetry, i.e. the number returned by this function. The first element positions[0] always contains a shift value of 0 representing the trivial rotation.

Note: Do not forget to release the memory occupied by positions after a successful execution of this function.

See also: vrna_rotational_symmetry_db(), vrna_rotational_symmetry_pos(), vrna_rotational_symmetry_pos_num()

Parameters

fc	A fold_compound data structure containing the nucleic acid sequence(s), their order, and model settings
structure	The dot-bracket structure the degree of rotational symmetry is checked for
positions	A pointer to an (undefined) list of alternative string start positions that lead to an identity mapping (may be NULL)

Returns: The degree of rotational symmetry of the structure (0 in case of any errors)

SWIG Wrapper Notes:: This function is attached as method rotational_symmetry_db() to objects of type fold_compound (i.e. vrna_fold_compound_t). Thus, the first argument must be omitted. In contrast to our C-implementation, this function doesn't simply return the order of rotational symmetry of the secondary structure, but returns the list position of cyclic permutation shifts that result in a rotationally symmetric structure. The length of the list then determines the order of rotational symmetry.

Detailed Description

Files

Functions

Function Documentation