Sekvenssammenstilling

I sekvenssammenstilling (engelsk sequence alignment) sammenligner man to eller flere strenger som for det meste er nukleotid- eller aminosyresekvenser. Noen av de første applikasjonene i bioinformatikk ble utviklet for sammenligning av sekvenser på 1970-tallet. I dag er sekvenssammenstilling en viktig del av genomforskning og  fylogenetiske analyser.

Typiske problemstillinger

Sammenstilling av sekvenser kan vise om to eller flere gener eller proteiner er beslektet («homologe»). Derfor er sekvensene i en sammenstilling arrangert slik at likheten er størst mulig. Om likheten er signifikant bedre enn man skulle forvente ved en tilfeldighet, kan man konkludere med at sekvensene er beslektet. 
For sekvenser fra både proteiner og DNA betyr slektskapet blant annet at funksjonen og strukturen ligner. Sekvenser fra en og samme art eller fra ulike arter kan sammenstilles. Likheter mellom ulike arter er ofte visualisert med fylogenetiske trær som viser den evolusjonære utviklingen av artene fra, vanligvis ukjente og derfor hypotetiske, forfedre.

Hovedprinsipper

Sammenstillingen av to sekvenser kalles parvis sammenstilling, ellers snakker man om multiple sammenstillinger. I parvis sammenstilling skiller man videre mellom global, lokal eller semiglobal sammenstilling.
Prinsippet i sekvenssammenstillingen er at man tilordner elementer (dvs. enten nukleotider eller aminosyrer) av en sekvens til elementene av en annen (eller flere) sekvens(er). Rekkefølgen av elementer blir den samme, og hvert element av den første sekvensen blir tilordnet til et annet element eller et såkalt  gap  (mellomrom). Hvis to elementer som ikke er identiske blir tilordnet til hverandre, så snakker man om en substitusjon (utbytting). Et gap er et tegn på enten en delesjon (sletting) eller en innsetting. Det er også lov å føye inn gap av lengde større en 1 for å sikre en meningsfull sammenstilling. Både substitusjon, gap, delesjon og innsetting er resultatet av mutasjoner.
Elementer som blir tilordnet hverandre er ofte identiske eller i hvert fall liknende. Mange identiske eller liknende elementer i samme rekkefølge peker på en evolusjonær eller funksjonell avhengighet.

Kostnadsfunksjoner (Scoring)

For å finne en optimal sammenstilling bruker man en scoringfunksjon som består av scorer for «match» (identiske elementer), «mismatch» (substitusjon) og gaps (innsetting/delesjon).
Et enkelt vurderingsskjema er for eksempel: +1 for en «match», -1 for en «mismatch», og -2 for et gap [av lengde 1] (straff for innsetting eller delesjon). Scoringfunksjoner kan være mye mer kompliserte og detaljerte, siden to elementer som ikke er identiske kan være mer eller mindre liknende. Liknende betyr i denne sammenhengen at man prøver å finne en verdi for sannsynligheten for at et bestemt par av elementer opprinnelig var identiske, men at de har endret seg gjennom evolusjonen. Derfor bruker man en såkalt scoring eller likhetsmatrise. Der finnes en score for hvert par av aminosyrer eller nukleotider som kan være både positiv eller negativ. For identiske elementer er scoren høy, for liknende elementer mindre, og svært forskjellige elementer har en negativ score. Vanlige scoringsmatriser er PAM 250 (for nukleotider) eller BLOSUM. Den siste er brukt i BLAST algoritmen.    
For å finne opprinnelsen av innsetting eller delesjon i evolusjonen bruker man de såkalte affine gap scores. De er empirisk motivert og som har en konstant score for gapåpning og en annen del som vokser lineart med lengden av gappet.
Totalscoren av en sammenstilling er summen av alle match-, mismatch- og gap-scores. En sammenstilling med den høyeste scoren kalles en optimal sammenstilling, men det kan være flere optimale sammenstillinger.

Globale sammenstillinger

Global sammenstilling brukes for å finne ut om sekvenser er homologe eller hvor nært beslektet de er. Man sammenstiller to eller flere hele sekvenser, dvs. alle elementer av sekvensene blir brukt i sammenstillingen. Denne metoden brukes ofte når sekvensene er omtrent like lange og når man forventer et nært slektskap.

Lokale sammenstillinger

Lokale sammenstillinger brukes for å finne ut om sekvenser inneholder deler som er homologe til hverandre eller finne ut hvor nært beslektet de er. 
Ofte forventer man ikke likhet på hele lengden, for eksempel når en sekvens er en sub-sekvens av den andre eller når sekvensene har overlappende ender. Et praktisk eksempel er å finne identiske sekvensmotiver i proteiner. 
Bare deler av sekvensene er inkludert i en lokal sammenstilling.

Semiglobale sammenstillinger

Semiglobale sammenstillinger brukes for å finne ut om en sekvens er homolog til deler av en annen. Lengden av sekvensene er ofte svært forskjellig. For beregningen av score teller man bare interne gaps, ikke gaps i enden av sekvensen.

Algoritmer for sekvenssammenstilling

Etter hvert har datamengdene blitt for store til å analysere DNA-sekvenser manuelt. Derfor er det behov for smarte algoritmer som kan anvendes på veldig lange sekvenser og store databaser. I sekvensanalyse brukes dynamisk programmering og heuristiske algoritmer. Dynamisk programmering gir optimale resultater, men krever store dataressurser og kan derfor være tidkrevende og upraktisk, mens heuristikker gjør det mulig å søke i de store, globalt tilgjengelige databasene som inneholder milliarder av nukleotider. Folk som jobber med bioinformatikk eller molekylærbiologi bruker for eksempel algoritmer og verktøy som BLAST for å oppdage mutasjoner i DNA-sekvenser. Disse algoritmene brukes også for å sette sammen alle sekvensene som har blitt sekvensert i et genomprosjekt til et helt genom (engelsk: (genome) assembly). 
Kjente algoritmer er Needleman-Wunsch-Algoritmen som gir en effektiv løsning for sammenligningen av to sekvenser og Smith-Waterman-Algoritmen for lokale sekvenssammenstillinger.

Andre bruksområder

Sekvenssammenstilling kan også brukes for å løse problemer knyttet til nøyaktig likhet av korte sekvensbiter, for eksempel det å finne DNA-sekvenser som restriksjonsenzymer gjenkjenner, eller automatisk søk etter regulatoriske sekvenser i et genom. Ikke alle delene i genomet er gener, og noen later ikke til å ha noen hensikt, disse kalles junk-DNA.