如何组合周期序列

Question

我有一个DNA序列，像CCG ACG GCA CTG GGC CAG TTG

我想在不改变每个子集的顺序的情况下，对这个序列进行所有可能的组合（比如说CCG应该是CCG）。 例如 修改后的序列可以是

ACG CCG GCA CTG GGC CAG TTG   # Here the first two sub-sets are interchanged.
GCA ACG CCG CTG GGC CAG TTG   # Here the first and third sub-sets are interchanged.

有没有简单的方法可以使用shell脚本或python代码来提供所有可能的组合

在每种可能的组合中，它都将涵盖这七个子集

Answer 1

使用支持长度（数组）的awk（现在应该是大多数awk）：

$ cat permutations.awk
###################
# Calculate all permutations of a set of strings, see
# https://en.wikipedia.org/wiki/Heap%27s_algorithm

function get_perm(A,            i, lgth, sep, str) {
    lgth = length(A)
    for (i=1; i<=lgth; i++) {
        str = str sep A[i]
        sep = " "
    }
    return str
}

function swap(A, x, y,  tmp) {
    tmp  = A[x]
    A[x] = A[y]
    A[y] = tmp
}

function generate(n, A, B,      i) {
    if (n == 1) {
        B[get_perm(A)]
    }
    else {
        for (i=1; i <= n; i++) {
            generate(n - 1, A, B)
            if ((n%2) == 0) {
                swap(A, 1, n)
            }
            else {
                swap(A, i, n)
            }
        }
    }
}

function get_perms(A,B) {
    generate(length(A), A, B)
}

###################

# Input should be a list of strings
{
    split($0,A)
    delete B
    get_perms(A,B)
    PROCINFO["sorted_in"] = "@ind_str_asc"
    for (perm in B) {
        print perm
    }
}

$ echo 'CCG ACG GCA' | awk -f permutations.awk
ACG CCG GCA
ACG GCA CCG
CCG ACG GCA
CCG GCA ACG
GCA ACG CCG
GCA CCG ACG

上面包含一个GNU ismPROCINFO[]，但它在其他AWK中也可以正常工作，该部分将被忽略，输出将不会被排序，但如果您愿意，您可以始终将其管道传输到sort

有关如何获得组合，请参见https://stackoverflow.com/a/56916316/1745001

Answer 2

虽然比python版本慢得多，但一个纯bash脚本打印其参数的排列：

#!/usr/bin/env bash

shopt -s lastpipe

permutations() {
    if [[ $# -gt 1 ]]; then
        local -a elems=( "$@" )
        local i curr result
        for (( i = 0; i < $#; i++ )); do
            curr="${elems[i]}"
            unset "elems[i]"
            permutations "${elems[@]}" | while read -r result; do
                printf "%s %s\n" "$curr" "$result"
            done
            elems[i]="$curr"
        done
    elif [[ $# -eq 1 ]]; then
        printf "%s\n" "$1"
    fi
}

permutations "$@"

它只是使用一种简单的递归方法来计算列表的所有排列

$ bash perms.sh CCG ACG GCA CTG GGC CAG TTG
CCG ACG GCA CTG GGC CAG TTG
CCG ACG GCA CTG GGC TTG CAG
CCG ACG GCA CTG CAG GGC TTG
CCG ACG GCA CTG CAG TTG GGC
CCG ACG GCA CTG TTG GGC CAG
CCG ACG GCA CTG TTG CAG GGC
...
many more lines
...
TTG CAG GGC CTG GCA ACG CCG
$

Answer 3

您可以使用itertools中的前提条件，例如：

import itertools

dna = "CCG ACG GCA CTG GGC CAG TTG"
dna = dna.split()

for combination in itertools.permutations(dna):
    print(combination)

我首先做了一个split（），它创建了一个由空格分隔的原始dna字符串数组，如下所示：

['CCG', 'ACG', 'GCA', 'CTG', 'GGC', 'CAG', 'TTG']

然后使用itertools.permutation（）返回该数组索引的所有组合