Parte 2: Alinhamento de Várias Seqüências

Descrição

Nesta segunda parte, vamos implementar uma heurística para o alinhamento de várias seqüências usando a pontuação SP.

Implemente o algoritmo estrela, ou um algoritmo que faça alinhamentos progressivos, ou alguma variação desses.

Você pode escolher se quer implementar um algoritmo penalizando ou não abertura de buracos. Porém, o seu algoritmo não deve penalizar buracos nas extremidades. Afora isso, seu algoritmo deve usar as pontuações adotadas na Parte 1 do projeto.

Você deve analisar a complexidade de seu algoritmo para alinhar k seqüências de comprimento no máximo n em função de k, n e l, o comprimento do alinhamento. Faça a análise de complexidade tanto do tempo --número de operações-- como do espaço --uso de memória.

Teste o seu algoritmo com as seqüências usadas na Parte 1 do projeto.

Para testar e comparar alinhamentos você também pode dar uma olhada no site ftp://ftp.ebi.ac.uk/pub/databases/embl/align/ que contém vários conjuntos de seqüências de DNA alinhadas.

Entrada e Saída

Como entrada você deve considerar as seqüências dadas no mesmo formato FASTA da Parte 1.

Considere que todas as seqüências estão armazenadas em um único arquivo. Como exemplos, você pode pegar aqui o arquivo contendo as seqüências da Parte 1.

Como saída o seu programa deverá imprimir pelo menos a pontuação do alinhamento e mais uma representação das seqüências alinhadas. Como exemplo da representação do alinhamento, reproduzo abaixo as primeiras 120 colunas obtidas para o alinhamento de nossas seqüências pelo Clustal W.

CLUSTAL W (1.83) multiple sequence alignment

AY425731        -----------------------------TWAACGAAAGCAGCAAAACAAGTCAAAAACT
AY425732        AAGGTTTCTTGTTTCGCTTTATCG-ATGATAAACGAAAGCAGCAAAACAAGTCAAAAACT
AY030387        -AAGGTTTCTGTTTCGCTTTATCG-ATGATAAACGAAAGCAGCAAAACAAGTCAAAAACT
AY425730        AAAGGTTTCTGTTTCGCTTTATCG-ATGATAAACGAAAGCAGCAAAACAAGTCAAAAACT
AY425739        AAAGGTTTCTGTTTCGCTTTATCGCACGATAAACGAAAGCAGCAAAACAAGCCAAAAACT
AY425741        AAAGGTTTCTGTTTCGCTTTATCGCACGATAAACGAAAGCAGCAAAACAAGCCAAAAACT
AY425740        AAAGGTTTCTGTTTCGCTTTATCGCACGATAAACGAAAGCAGCAAAACAAGCCAAAAACT
AY425735        AAAGGTTTCTGTTTCGCTTTATCGCACGATAAACGAAAGCAGCAAAACAAGCCAAAAACT
AY425737        AAAGGTTTCTGTTTCGCTTTATCGCACGATAAACGAAAGCAGCAAAACAAGCCAAAAACT
AY425733        AAAGGTTTCTGTTTCGCTTTATCGCACGATAAACGAAAGCAGCAAAACAAGCCAAAAAAA
AY425736        AAAGGTTTCTGTTTCGCTTTATCGCACGATAAACGAAAGCAGCAAAACAAGCCAAAAACT
AY425734        AAAGGTTTCTGTTTCGCTTTATCGCACGATAAACGAAAGCAGCAAAACAAGCCAAAAACT
AY425738        AAAGGTTTCTGTTTCGCTTTATCGCACGATAAACGAAAGCAGCAAAACAAGCCAAAAACT
AY425742        AARGTTTCTTGTTGC----TATCG-ACGA-AAACGAAAGCAGCATAAAAAG-CAAACACG
AY425743        AAAGGTTTCTTTTTT--TTGCTCGCAAAAGCAAAAAAATGACTCGCTAAAATGACAAACT
AY425744        AAAGGTTTCTTTTTT--TTGCTCGCAAAAGCAAAAAAATGACTCGCTAAAATGACAAACT
                                               **  ***  *       **   * * *  

AY425731        CTC---GTCTCATTGCCAGCCGGGGGCGTCGAAGCGCACGAAGCGCCGCTCTGGCTGGTA
AY425732        CTC---GTCTCATTGCCGGCCGGGG-CGTCGAAGCGCACGAAGCGCCGCTCTGGCTGGTA
AY030387        CTC---GTCTCATTGCCGGCCGGGG-CGTCGAAGCGCACGAAGCGCCGCTCTGGCTGGTA
AY425730        CTC---GTCTCATCGCCGGCCGGGG-CGTCGAAGCGCACGAAGCGC-GCTCTGGCTGGTA
AY425739        CCT--CGTCTCATTGCCGGCCGGGG-CGTCGAAGCGCACGAAGCGCCGCTCTGGCTGGTA
AY425741        CCT--CGTCTCATTGCCGGCCGGGG-CGTCGAAGCGCACGAAGCGCCGCTCTGGCTGGTA
AY425740        CCT--CGTCTCATTGCCGGCCGGGG-CGTCGAAGCGCACGAAGCGCCGCTCTGGCTGGTA
AY425735        CCT--CGTCTTATTGCCGGCCGGGG-CGTCGAAGCGCACGAAGCGCCGCTCTGGCTGGTA
AY425737        CCTT-CGTCTCATTGCCGGCCGGGG-CGTCGAAGCGCACGAAGCGC-GCTCTGGCTGGTA
AY425733        CTCCACGTCTCATTGCCGGCCGGGG-CGTCGAAGCGCACGAAGCGCCGCTCTGGCTGGTA
AY425736        CCT--CGTCTCATTGCCGGCCGGGG-CGTCGAAGCGCACGAAGCGCCGCTCTGGCTGGTA
AY425734        CCA--CGTCTCATTGCGGCCCGGGG-CGTCAAAGCGCACGAAGCGCCGCTCTGGCTGGTA
AY425738        CCT--CGTCTCATTGCCGGCCGGGG-CGTCGAAGCGCACGAAGCGCCGCTCTGGCTGGTA
AY425742        CAC---AAAAAACAGCCGGCCCGGGGCGTCGAAGCGCACGAAGCGCCGCTCTGGCCGGTA
AY425743        CGT---CAAACACGACCGGCCGGGG-CGTCGAAGCGCACGAAGCGCCGCACTGGCTGGTA
AY425744        CGT---CAA-CACGACCGGCCGGGG-CGTCGAAGCGCACGAAGCGCCGCACTGGCTGGTA
                *          *   *   ** *** **** *************** ** ***** ****

O que entregar

• Seu programa.
• Relatório comentando o trabalho feito, contendo:
  • descrição do algoritmo que você implementou, incluindo qual o esquema de pontuação que foi usado;
  • a análise do algoritmo;
  • comentários dos testes feitos;
  • uma seção com um manual de uso de seu programa, contendo instruções de como compilar e testar o seu programa. Informe também o compilador que você usou para testar o programa.