Rhobincu: /* Date de ieșire */

2015-05-04T17:19:54Z

Date de ieșire

Rhobincu: /* Date de ieșire */

2015-05-04T17:19:37Z

Date de ieșire

Rhobincu: /* Date de intrare */

2015-05-04T17:18:53Z

Date de intrare

Rhobincu: Pagină nouă: Î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 (m...

2015-05-04T17:17:28Z

Pagină nouă: Î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 (m...

Pagină nouă

Î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:
# indexarea referinței;
# 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 [http://en.wikipedia.org/wiki/FASTA_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'''.

'''<font color="red">Atenție:</font>''' 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ă.

'''<font color="red">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.</font>'''

@@ Linia 36: / Linia 36: @@
 Exemplu:
   seq0000001,222,234
-  seq0000002,
+  seq0000002
   seq0000003,211

@@ Linia 32: / Linia 32: @@
 == 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.
+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:

@@ Linia 21: / Linia 21: @@
   AGATGGATTGCAGCATGCGCGACGCATCGCGCAGCATTCAGACGACACCACCCCAATATTAAATCTTACATAAGTCCTTTTCAAAGTC
-Fișierul cu secvențele de intrare va fi un fișier format [http://en.wikipedia.org/wiki/FASTA_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ă.
+Fișierul cu secvențele de intrare va fi un fișier format [http://en.wikipedia.org/wiki/FASTA_format fasta] simplificat, numit '''sequences.fasta'''. 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:

SDA Tema 3 - Revizia istoricului

Rhobincu: /* Date de ieșire */

Rhobincu: /* Date de ieșire */

Rhobincu: /* Date de intrare */

Rhobincu: Pagină nouă: Î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 (m...