Key points are not available for this paper at this time.
O alinhamento rigoroso de múltiplas sequências de proteínas torna-se impraticável mesmo com um número modesto de sequências, já que os requisitos de memória e tempo de computador aumentam como o produto dos comprimentos das sequências. Nós elaboramos uma estratégia para abordar um alinhamento ótimo, que modifica os requisitos intensivos de armazenamento e tempo de programação dinâmica. Nosso algoritmo divide aleatoriamente um grupo de sequências não alinhadas em dois subgrupos, entre os quais um alinhamento ótimo é então obtido por um algoritmo no estilo Needleman-Wunsch. Nosso algoritmo utiliza uma matriz com dimensões correspondentes aos comprimentos dos dois subgrupos de sequências alinhadas. O processo de alinhamento par a par é repetido usando diferentes divisões aleatórias do grupo inteiro em dois subgrupos. Comparado com a abordagem rigorosa de resolver a rede n-dimensional por programação dinâmica, nosso algoritmo iterativo resulta em alinhamentos que correspondem ou estão próximos da solução ótima, em um conjunto limitado de problemas de teste. Implementamos este algoritmo em um programa de computador que roda em máquinas da classe IBM PC, juntamente com um ambiente amigável para o usuário para selecionar interativamente sequências ou grupos de sequências a serem alinhados simultaneamente ou progressivamente.
Berger et al. (Ter,) estudaram esta questão.