SDA Tema 3

În domeniul bioinformaticii, una din cele mai acute probleme este alinierea rapidă și cât mai corectă a secvențelor de ADN pe un șir de referință. Dându-se un număr mare (milioane) de secvențe scurte (între 15 și 100 de baze), se cere pentru fiecare aflarea indecșilor la care se pot regăsi acestea într-un singur șir de referință foarte lung (miliarde de baze). Acest lucru este cu atât mai dificil cu cât alinierea nu este neapărat bază la bază, ci pot apărea mutații sub forma de inserții, eliminări sau inversii de baze.

Pentru această temă, vom simplifica cerința, considerând aliniera a fi perfectă, prin urmare se vor considera indecșii corecți doar acolo unde secvența apare în întregime și nemodificată în referință.

Cerință

Dându-se o referință de ADN de maximum 500.000.000 de baze (notate cu A, C, G, T) și un număr N, nelimitat de mare de secvențe de 5 sau 6 baze (notate tot cu A, C, G, T), să se găsească în referință, pentru fiecare secvență, indecșii la care apare.

Informații suplimentare

Algoritmul va consta în două etape:

1. indexarea referinței;
2. pentru fiecare secvență în parte, căutarea indecșilor în dicționar și printarea rezultatelor.

Date de intrare

Fișierul de referință, numit reference.txt va conține exclusiv caractere A, C, G și T și spații albe (spațiu, tab, new-line) care se ignoră.

Exemplu:

AAACTCGCTAGATCCGATCGATAAGCATAGCATCAGACATTTTGACATAGAAATGGGCATACCCCTAGATAGCATCGA
GATAGCTTAGCATATCGCATACTAACCATCAGCATCTACGATTGGCATATAGCATGCATTTACACCGATGCAG
AGATGGATTGCAGCATGCGCGACGCATCGCGCAGCATTCAGACGACACCACCCCAATATTAAATCTTACATAAGTCCTTTTCAAAGTC

Fișierul cu secvențele de intrare va fi un fișier format fasta simplificat. Fiecare secvență va fi definită de două linii. Prima linie va începe cu caracterul > (mai mare) după care apare ID-ul secvenței, iar pe cea de-a doua linie va fi secvența efectivă.

Exemplu:

>seq0000001
AAGTC
>seq0000002
ATTGTC
>seq0000003
AAATCT

Date de ieșire

Rezultatul programului va fi un fișier csv numit (aligner_results.csv) unde primul câmp de pe linie va fi ID-ul secvenței, apoi în ordine indecșii unde apare secvența în referință, sau nimic daca secvența respectivă nu apare.

Exemplu:

seq0000001,222,234
seq0000002,
seq0000003,211

Restricții

• Pentru indexare (construirea dicționarului) se va folosi un arbore de prefixe.

Livrabile

Tema submisă va conține: unul sau mai multe fișiere .cpp/.c/.h care să fie compilabile pe cel puțin o platformă (sistem de operare + compilator), și un document pdf care să conțină o analiză a complexității în timp și spațiu. Documentul va conține și o sugestie de implementare pentru un program care să alinieze secvențe de orice lungime.

Modalitatea de submitere

Tema va fi submisă pe e-mail, la adresa homework@dcae.pub.ro. Subiectul va fi [SDA-3][NUME][GRUPA]. Fișierele vor fi atașate mesajului, NEARHIVATE.

Atenție: Singurul fișier binar va fi documentul pdf. Orice alt binar (executabil, dll, so, etc.) atașat mesajului va face ca acesta să fie respins de server-ul de e-mail și în consecintă să nu primiți nici un punct pe temă.

Atenție: Temele vor fi verificate anti-plagiat cu soft-uri specializate. Orice temă copiată va fi penalizată (atât sursa cât și copia) cu 100% din punctaj, fără posibilitate de refacere.