1

2

StringheStringhe

Stringa = dato che non si scompone, ma puo’ essere scritto come una lunga sequenza di caratteri

• abbbabababcbabcccba• 01010001001010• Nel#mezzo#del#cammin#di#nostra#vita#• ACCCATGATCGTACTCG

3

Algoritmi e strutture dati su stringheAlgoritmi e strutture dati su stringhe

• Text editing• Linguistica computazionale• Compressione di dati• Biologia computazionale

Nota: alcune delle slides seguenti sono tratte da http://www.theory.lcs.mit.edu/ e dahttp://www.ornl.gov/hgnis

Applicazioni principali:

4

TextText editingediting

• grep string-matching, regular-expression-matching

• agrep approximate-pattern-matching• sed repetition-finding, pattern-matching• awk multi-pattern-matching• lex regular-expression-matching• yacc e twig tree-pattern-matching• diff LCS, edit-distance

Esempio: alcuni comandi e linguaggi in Unix

5

Linguistica Linguistica computazionalecomputazionale

Dizionario = testo statico organizzato in modo da velocizzare gli accessi

(per esempio tramite indice)

Applicazioni :• Parsing linguaggi naturali • Image processing (2D-pattern-matching,

dictionary-of-sub-images)

Alcune strutture dati per indici sono:

suffix-trees, suffix-arrays, DAWG, Factor-automata

6

Compressione dei datiCompressione dei dati

• Compressione di testi • Compressione di immagini o suoni

Applicazioni: • telecomunicazioni (fax,…) • analisi linguaggi naturali (dizionari, …) • biologia computazionale• …

Importante: ridondanze e regolarita’ nel testo

7

8

9

Biologia molecolareBiologia molecolareLe molecole di DNA e RNA in un primo approccio,

possono essere viste come stringhe:

DNA: CAGCTGATCGATGCTAGCCTGRNA: ACGUACGUAUUGCAUCGUAC

Alfabeto dei nucleotidi (basi, bp):A = adenina, C = citosina, G =guanina, T = timina

U = uracileA - T C - G

10

11

12

Studiare il DNAStudiare il DNA

• Sequencing = determinare la sequenza completa dei nucleotidi(A,C,G,T) di una lunga stringa di DNA

Ø trascrizione dal gel

Ø ricostruzione (fragment assembly)

• Collezione: costruzione e ricerca in enormi database

• Analisi: Ø Mapping

Ø Alignment

Ø Ricerca di similarita’, ridondanze, regolarita’

Ø …grande quantita’ di algoritmi su stringhe…

13

GenomaGenoma

Il genoma e’ tutto il DNA in un organismo

• http://www.pbs.org/wgbh/nova/genome/• http://www.ornl.gov/hgmis/ (Human Genome Project)• http://gdbwww.gdb.org/gdb/report.html (Genome

Database)• …

Nota: strutture dati centrali in alcuni progetti genome-scalesono suffix-trees, generalized-suffix-trees e suffix-arrays

14

HumanHuman GenomeGenome ProjectProject

Begun in 1990, the U.S. Human Genome Project is a 13-year effortcoordinated by the Department of Energy and the National Institutesof Health. The project originally was planned to last 15 years, buteffective resource and technological advances have accelerated the expected completion date to 2003. Project goals are to

• identify all the approximately 30,000 genes in human DNA,

• determine the sequences of the 3 billion chemical base pairsthat make up human DNA,

• store this information in databases, • improve tools for data analysis, • transfer related technologies to the private sector, and • address the ethical, legal, and social issues (ELSI) that may arise

from the project. • Several types of genome maps have already been completed, and a

working draft of the entire human genome sequence wasannounced in June 2000, with analyses published in February 2001.

15

Q. Q. HowHow big big isis the the humanhuman genomegenome??

The human genome is made up of DNA, which has four different chemicalbuilding blocks. These are called bases and abbreviated A, T, C, and G. In the human genome, about 3 billion bases are arranged along the chromosomes in a particular order for each unique individual. To get anidea of the size of the human genome present in each of our cells, consider the following analogy: If the DNA sequence of the humangenome were compiled in books, the equivalent of 200 volumes the size of a Manhattan telephone book (at 1000 pages each) would beneeded to hold it all.

It would take about 9.5 years to read out loud (without stopping) the 3 billion bases in a person's genome sequence. This is calculated on a reading rate of 10 bases per second, equaling 600 bases/minute, 36,000 bases/hour, 864,000 bases/day, 315,360,000 bases/year.

Storing all this information is a great challenge to computer experts knownas bioinformatics specialists. One million bases (called a megabase and abbreviated Mb) of DNA sequence data is roughly equivalent to 1 megabyte of computer data storage space. Since the human genome is3 billion base pairs long, 3 gigabytes of computer data storage space are needed to store the entire genome. This includes nucleotidesequence data only and does not include data annotations and otherinformation that can be associated with sequence data.

16

Studiare il DNA: Studiare il DNA: sequencingsequencing

Sequencing una piccola porzione di DNA (circa 500 bp) e’ fattibile (tramite macchinari o a mano) mentre una lunga no.

Sequencing di una lunga porzione si ottiene mettendo tutti i pezzi piccoli in un computer. Il problema e’ di rimettere insieme i pezzi correttamente (fragment assembly).

17

18

19

Problemi algoritmici nel Problemi algoritmici nel sequencingsequencing

• Trascrizione (2D-pattern-matching)

• Fragment assembly (shortest-superstring, suffix-prefix)

20

Studiare il DNA: collezioneStudiare il DNA: collezione

Gli archivi di sequenze e il software per la ricerca in essi sono diventati strumenti essenziali nella moderna biologia molecolare

• I piu’ grandi archivi contengono sequenze per una lunghezza totale di miliardi di nucleotidi; questi numeri crescono di circa il 75% all’anno

• Il ‘nonno’ degli archivi e’ GenBank, incaricato di mantenere tutte le sequenze di DNA mai rese pubbliche

• In Europa Swiss-Prot e’ il piu’ grande archivio di sequenze di proteine con centinaia di migliaia di richieste al mese

21

Studiare il DNA: analisi di sequenze Studiare il DNA: analisi di sequenze biologichebiologiche

• Mapping = specificare le locazioni dove compaiono markers o copie di sottostringhe di interesse (shortest-superstring, suffix-prefix)

• Alignment = allineare sequenze di caratteri inserendo spazi e permettendo ‘match’ e ‘mismatch’ fra i caratteri corrispondentiUn alignment di qacdbd e qawxb:

q a c _ d b dq a w x _ b _

Dualita’ con edit-transcription e edit-distance (programmazione dinamica). Varianti coinvolgono LCS, approximate-string-matching

• Ricerca similarita’, ridondanza e regolarita’

• …

22

Regolarita’Regolarita’Molte tecniche algoritmiche su stringhe molecolari sfruttano

regolarita’ e ripetitivita’ nelle stringhe

Strutture ripetitive nel DNA :• Palindrome : abccba, ‘was it a cat i saw’• Palindrome complementate: AGCTCGCGAGCT• Tandem arrays: TTAGGG si ripete alla fine di ogni

cromosoma umano• Alu repeats: sottostringhe di circa 300 bp che si

presentano quasi identiche in tutto il genoma umano (ogni frammento di DNA umano piu’ lungo di 20.000 bpne contiene una) e contengono esse stesse ripetizioni di sottostringhe di circa 40 bp e spesso dei tandem arrays

• ….

23

StringString--matchingmatching‘’Il problema su stringhe fondamentale’’

• Fondamentale in molte applicazioni

• Compare come sottoproblema (per esempio: in biologia molecolare e’ sottoproblema di multiple-sequence-comparison, large-scale sequence-comparison, database-searching, …)

• Tecniche per string-matching si estendono ad altri problemi (per esempio: 2D-pattern-matching, string-matchingapprossimato, …)

Nota: approssimato = alcuni errori di vario tipo sono ammessi. E’ centrale in biologia molecolare.

24

StringString--matchingmatching

• Testo = stringa di lunghezza n• Pattern = stringa di lunghezza m• Problema = trova le occorrenze del pattern nel

testo (tutte o 1)

AGGCTCACGTATATATGCGTTATAATG

TATATATA

TATA

25

Algoritmi per Algoritmi per stringstring matchingmatching

O(|Σ|n + m)Preprocess testo (o pattern)Suffix-trees

Piccoli patternShift-And

Caso medioRK

O(n+|Σ|m)Preprocess pattern; real-timesearch

Automi

O(n + m) in media

Preprocess patternBM

O(n + m)Preprocess patternKMP

O(n m )Naif

26

Programma corsoProgramma corso

Ø Introduzione e motivazioni

Ø Suffix-trees, generalized suffix-trees: string matching, longest-

common-substring, suffix-prefix (GUS 5.1,5.2,5.3,5.4, 6.4, 7.1,7.4, 7.10)

Ø Shortest-superstring approssimato (GUS 16.17, Vaz 2.3,)

Ø 2D pattern matching

Ø Regolarita’

D. Gusfield, Algorithms on Strings, Trees, and Sequences - Computer

Science and Computational Biology, Cambridge Univ. Press 1997

27

Similarita’Similarita’

Primo fatto dell’analisi di sequenze biologiche:‘’Nelle sequenze biomolecolari (DNA, RNA, …)

una alta similarita’ fra sequenze di solito implica una significativa similarita’ strutturale o funzionale’’

‘’…everything in life is so similar, that the samegenes that work in flies are the ones that work in humans’’ (Wieschaus, Premio Nobel 1995)

28

RidondanzaRidondanza

‘’The vast majority of extant proteins are the result of a continous series of duplicationsand subsequent modifications. As a result, … so many new sequences resemblealready known sequences.’’ (Doolittle)

‘’…all of biology is based on an enormousredundancy…’’ (Doolittle)