Combinatorics Algorithms

Implementations to solve various combinatorial aspects for strings of objects.

Functions

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 Sawada [2003] .

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.

SWIG Wrapper Notes:

This function is available as global function enumerate_necklaces() which accepts lists input, an produces list of lists output. See, e.g. RNA.enumerate_necklaces() in the Python API .

Parameters:

  • type_counts – A 0-terminated list of entity counts

Returns:

A list of all non-cyclic permutations of the entities

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.

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. See, e.g. RNA.rotational_symmetry() in the Python API .

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

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.

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. See, e.g. RNA.rotational_symmetry() in the Python API .

See also

vrna_rotational_symmetry_num(), vrna_rotational_symmetry(), vrna_rotational_symmetry_pos()

Note

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

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

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.

SWIG Wrapper Notes:

This function is available as global function rotational_symmetry(). See vrna_rotational_symmetry_pos() for details. See, e.g. RNA.rotational_symmetry() in the Python API .

See also

vrna_rotational_symmetry_pos(), vrna_rotationa_symmetry_num()

Parameters:

  • string – A NULL-terminated string of characters

Returns:

The order of rotational symmetry

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.

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. See, e.g. RNA.rotational_symmetry() in the Python API .

See also

vrna_rotational_symmetry(), vrna_rotational_symmetry_num(), vrna_rotational_symmetry_num_pos()

Note

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

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

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.

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. See, e.g. RNA.fold_compound.rotational_symmetry_db() in the Python API .

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)

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.

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. See, e.g. RNA.fold_compound.rotational_symmetry_db() in the Python API .

See also

vrna_rotational_symmetry_db(), vrna_rotational_symmetry_pos(), vrna_rotational_symmetry_pos_num()

Note

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

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)

unsigned int **vrna_n_multichoose_k(size_t n, size_t k)
#include <ViennaRNA/combinatorics.h>

Obtain a list of k-combinations with repetition (n multichoose k)

This function compiles a list of k-combinations, or k-multicombination, i.e. a list of multisubsets of size k from a set of integer values from 0 to n - 1. For that purpose, we enumerate n + k - 1 choose k and decrease each index position i by i to obtain n multichoose k.

Parameters:

  • n – Maximum number to choose from (interval of integers from 0 to n - 1)

  • k – Number of elements to choose, i.e. size of each multisubset

Returns:

A list of lists of elements of combinations (last entry is terminated by NULL

unsigned int *vrna_boustrophedon(size_t start, size_t end)
#include <ViennaRNA/combinatorics.h>

Generate a sequence of Boustrophedon distributed numbers.

This function generates a sequence of positive natural numbers within the interval \( [start, end] \) in a Boustrophedon fashion. That is, the numbers \( start, \ldots, end \) in the resulting list are alternating between left and right ends of the interval while progressing to the inside, i.e. the list consists of a sequence of natural numbers of the form:

\[ start, end, start + 1, end - 1, start + 2, end - 2, \ldots \]

The resulting list is 1-based and contains the length of the sequence of numbers at it’s 0-th position.

Upon failure, the function returns NULL

SWIG Wrapper Notes:

This function is available as overloaded global function boustrophedon(). See, e.g. RNA.boustrophedon() in the Python API .

See also

vrna_boustrophedon_pos()

Parameters:

  • start – The first number of the list (left side of the interval)

  • end – The last number of the list (right side of the interval)

Returns:

A list of alternating numbers from the interval \( [start, end] \) (or NULL on error)

unsigned int vrna_boustrophedon_pos(size_t start, size_t end, size_t pos)
#include <ViennaRNA/combinatorics.h>

Obtain the i-th element in a Boustrophedon distributed interval of natural numbers.

SWIG Wrapper Notes:

This function is available as overloaded global function boustrophedon(). Omitting the pos argument yields the entire sequence from start to end. See, e.g. RNA.boustrophedon() in the Python API .

See also

vrna_boustrophedon()

Parameters:

  • start – The first number of the list (left side of the interval)

  • end – The last number of the list (right side of the interval)

  • pos – The index of the number within the Boustrophedon distributed sequence (1-based)

Returns:

The pos-th element in the Boustrophedon distributed sequence of natural numbers of the interval