Projeto de sequência de ácidos nucleicos por meio da otimização eficiente do defeito do conjunto

Descrevemos um algoritmo para projetar a sequência de uma ou mais fitas de ácidos nucleicos interagentes destinadas a adotar uma estrutura secundária alvo em equilíbrio. O design de sequência é formulado como um problema de otimização com o objetivo de reduzir o defeito do conjunto abaixo de uma condição de parada especificada pelo usuário. Para uma sequência candidata e uma dada estrutura secundária alvo, o defeito do conjunto é o número médio de nucleotídeos emparelhados incorretamente em equilíbrio avaliado sobre o conjunto de estruturas secundárias não pseudo-nó. Para reduzir o custo computacional de aceitar ou rejeitar mutações a uma sequência inicial aleatória, as mutações candidatas são avaliadas nos nós folha de uma decomposição em árvore da estrutura alvo. Durante a otimização das folhas, a amostragem de mutações ponderadas pelo defeito é usada para selecionar cada posição de mutação candidata com probabilidade proporcional à sua contribuição para o defeito do conjunto da folha. À medida que subsequências são combinadas subindo a árvore, defeitos estruturais emergentes resultantes da interferência entre sequências irmãs são eliminados por reotimização dentro da subárvore defeituosa começando a partir de novas subsequências aleatórias. Usando um programa dinâmico Θ (N (3) ) para avaliar o defeito do conjunto de uma estrutura alvo com N nucleotídeos, essa abordagem hierárquica implica um limite de otimalidade assintótica sobre o tempo de design: para N suficientemente grande, o custo do design de sequência é limitado inferiormente por 4/3 do custo de uma única avaliação do defeito do conjunto para a sequência completa. Portanto, o algoritmo de design tem complexidade de tempo Ω (N (3) ). Para estruturas-alvo contendo N ∈100, 200, 400, 800, 1600, 3200 nucleotídeos e hastes de duplex variando de 1 a 30 pares de bases, os projetos de sequência de RNA a 37°C normalmente conseguem satisfazer uma condição de parada com defeito do conjunto inferior a N/100. Empiricamente, o algoritmo de design de sequência exibe otimalidade assintótica e o expoente no limite de complexidade de tempo é afiado.