Bioinformatics

# Introducció a l'ensamblatge de genomes Aquesta secció introdueix el concepte d'ensamblatge de genomes com una estratègia clau en bioinformàtica. Aborda la problemàtica general i esmenta la dificultat de resoldre problemes NP-complets en aquest context [19](#page=19) [23](#page=23). ### 1.1 La problemàtica general de l'ensamblatge de genomes L'objectiu de l'ensamblatge de genomes és reconstruir la seqüència completa d'un genoma a partir de fragments de seqüència més curts, coneguts com a "lectures" (reads). Aquest procés és anàleg a intentar reconstruir un llibre a partir de trossos de pàgines esquinçades. Les lectures es generen mitjançant tecnologies de seqüenciació, i la seva longitud i la presència d'errors de seqüenciació són factors clau que influeixen en la complexitat de l'ensamblatge [14](#page=14) [55](#page=55). > **Tip:** En la pràctica, les lectures tenen diferents longituds i contenen errors de seqüenciació. Tot i que encara es poden construir grafs de De Bruijn, els camins al llarg dels grafs no seran eulerià, cosa que afegeix dificultat a la reconstrucció del genoma [55](#page=55). ### 1.2 La dificultat computacional: problemes NP-complets L'ensamblatge de genomes sovint implica resoldre problemes que són computacionalment difícils, pertanyent a la classe NP-complets. Això significa que no existeix un algorisme eficient conegut que pugui trobar la solució òptima en un temps polinomial per a qualsevol instància del problema [19](#page=19). Les estratègies comunes per abordar els problemes NP-complets inclouen: * Aproximació [19](#page=19). * Randomització [19](#page=19). * Parametrització [19](#page=19). * Recerca heurística [19](#page=19). * I altres [19](#page=19). Aquestes aproximacions busquen trobar solucions bones o gairebé òptimes en un temps computacional raonable, en lloc d'esperar solucions perfectes que podrien ser introbablement llargues de calcular [19](#page=19). ### 1.3 Conceptes relacionats Durant la discussió sobre l'ensamblatge, s'han esmentat diverses estratègies i conceptes, com ara els grafs de De Bruijn i l'algorisme "Greedy". També s'ha introduït el principi del "string graph" de Myers, que implica l'eliminació d'arestes transitives en un graf de solapes per obtenir una representació més neta abans de l'ensamblatge [58](#page=58) [59](#page=59) [62](#page=62). > **Tip:** El principi del "string graph" de Myers permet eliminar arestes transitives a partir del graf de solapes per obtenir una representació mínima i més neta abans de procedir amb l'ensamblatge [62](#page=62). --- # Mètodes i algorismes d'ensamblatge Aquesta secció explora diverses estratègies i algorismes utilitzats en l'ensamblatge de genomes, incloent els grafs de De Bruijn, la resolució de problemes NP-complets mitjançant aproximació i heurístiques, i conceptes com els grafs de solapes. ### 2.1 Introducció a l'ensamblatge de genomes L'ensamblatge de genomes és el procés de reconstruir la seqüència completa d'un genoma a partir de fragments de seqüència més curts, coneguts com a "reads". Aquest procés s'enfronta a diversos reptes degut a la longitud variable de les reads i la presència d'errors de seqüenciació [55](#page=55). ### 2.2 Estratègies per resoldre problemes NP-complets en ensamblatge Molts problemes dins de l'ensamblatge de genomes són NP-complets. Per abordar aquests problemes, s'empren diverses estratègies [19](#page=19): * **Aproximació:** Trobar solucions que siguin properes a l'òptim, tot i que no necessàriament l'òptim exacte. * **Randomització:** Utilitzar elements aleatoris en l'algorisme per explorar diferents possibilitats de solució. * **Parametrització:** Simplificar el problema basant-se en certs paràmetres. * **Recerca heurística:** Empra mètodes que troben bones solucions en un temps raonable, sense garantir l'òptim. * Altres tècniques com les esmentades per Alan Turing [19](#page=19). ### 2.3 Grafs de De Bruijn Els grafs de De Bruijn són una eina fonamental per a l'ensamblatge de genomes. En aquest tipus de grafs, els nodes representen k-mers (subseqüències de longitud k) i les arestes connecten k-mers que difereixen en un sol nucleòtid per la dreta (o esquerra, depenent de la convenció) [58](#page=58) [59](#page=59). Quan les reads tenen diferents longituds i contenen errors, els camins en el graf de De Bruijn ja no són necessàriament eulerià. Això afegeix dificultat a la reconstrucció del genoma [55](#page=55). > **Tip:** Els grafs de De Bruijn són eficients per representar la informació de solapament entre k-mers d'un conjunt de reads. #### 2.3.1 Algorismes "Greedy" amb grafs de De Bruijn Els algorismes "greedy" aplicats als grafs de De Bruijn intenten trobar un camí que cobreixi totes les arestes (o nodes) del graf, sovint prenent la decisió localment òptima en cada pas [58](#page=58) [59](#page=59). ### 2.4 Grafs de solapes ("Overlap Graphs") Els grafs de solapes representen les relacions de solapament entre diferents fragments de seqüència (reads o contigs). Cada node pot representar una read o un contig, i una aresta indica que dues seqüències tenen un solapament suficient [62](#page=62). #### 2.4.1 El principi del "string graph" de Myers El principi del "string graph" proposat per Myers implica eliminar arestes transitives d'un graf de solapes. Aquesta eliminació d'arestes redundants redueix la complexitat del graf, resultant en una representació més neta i mínima abans de procedir a l'ensamblatge [62](#page=62). > **Tip:** La reducció de transitivitat en grafs de solapes simplifica el problema d'identificar la seqüència genòmica subjacent. ### 2.5 Qualitat de l'ensamblatge: N50 i N75 La qualitat d'un ensamblatge de genoma es mesura sovint utilitzant mètriques com N50 i N75. Aquestes mètriques quantifiquen la longitud dels contigs (seqüències contínues resultants de l'ensamblatge) [68](#page=68). * **N50:** És la longitud d'un contig tal que el 50% de les bases totals de l'ensamblatge es troben en contigs de longitud igual o superior a N50 [68](#page=68). * **N75:** És la longitud d'un contig tal que el 75% de les bases totals de l'ensamblatge es troben en contigs de longitud igual o superior a N75 [69](#page=69). Un valor de N50 (o N75) més elevat indica un ensamblatge de millor qualitat, amb contigs més llargs i menys fragmentació [69](#page=69). #### 2.5.1 Càlcul de N50 i N75 El càlcul de N50 i N75 implica els següents passos [70](#page=70) [71](#page=71): 1. **Obtenir longituds:** Recopilar les longituds de tots els contigs del ensamblatge. Si no hi ha contigs, es retorna (0, 0) [70](#page=70). 2. **Suma total de bases:** Calcular la suma total de les longituds de tots els contigs, que és una estimació del tamany del genoma [68](#page=68) [70](#page=70). 3. **Ordenar longituds:** Ordenar la llista de longituds de contigs de major a menor [70](#page=70). 4. **Definir umbrals:** Calcular els umbrals corresponents al 50% i 75% de la suma total de bases. Es calcula el sostre (`ceil`) d'aquests valors. Per exemple, per a un total de 188.1 Mb, el 50% és 94.05 Mb [68](#page=68) [70](#page=70). 5. **Acumular i trobar:** Recórrer la llista de longituds ordenades, acumulant les longituds. El valor de la longitud del contig que fa que la suma acumulada creixi per sobre del 50% és el N50. De manera similar, es troba el N75 quan s'assoleix el 75% del total [71](#page=71). > **Example:** Si tenim contigs amb longituds i la suma total és 3000 . > * N50: El 50% de 3000 és 1500. La suma acumulada seria: 1000 (acumulat 1000), 800 (acumulat 1800). El N50 seria 800, ja que 1800 > 1500. > * N75: El 75% de 3000 és 2250. La suma acumulada seria: 1000 (acumulat 1000), 800 (acumulat 1800), 600 (acumulat 2400). El N75 seria 600, ja que 2400 > 2250. ### 2.6 Ensambladors conservadors vs. agressius Hi ha una distinció entre diferents tipus d'ensambladors, sovint classificats com a "conservadors" o "agressius" [72](#page=72). * **Ensamblador conservador:** Sovint produeix pocs errors però resulta en molts contigs curts. * **Ensamblador agressiu:** Pot generar contigs llargs però pot introduir molts errors, resultant en un "borrador" del genoma [72](#page=72). La tria entre un tipus d'ensamblador o un altre depèn dels objectius de l'estudi i la qualitat de les dades de seqüenciació disponibles. --- # Qualitat de l'ensamblatge i formats de fitxer Aquesta secció explora les mètriques clau per avaluar la qualitat d'un ensamblatge genòmic i els formats de fitxer estàndard utilitzats en bioinformàtica, incloent com es codifiquen les puntuacions de qualitat. ### 3.1 Mètrica de qualitat de l'ensamblatge: N50 i N75 La qualitat d'un ensamblatge genòmic es pot mesurar mitjançant diverses mètriques, sent les més comunes el N50 i el N75. Aquestes mètriques proporcionen una visió ràpida de la continuïtat de l'ensamblatge [69](#page=69). #### 3.1.1 Definició de N50 i N75 * **N50:** La longitud $L$ d'un contig tal que el 50% de les bases totals de l'ensamblatge es troben en contigs de longitud igual o superior a $L$. En altres paraules, és la longitud del contig més curt que, quan tots els contigs iguals o més llargs es sumen, cobreixen la meitat de les bases del genoma ensamblat [68](#page=68). * **N75:** De manera anàloga al N50, el N75 és la longitud $L$ d'un contig tal que el 75% de les bases totals de l'ensamblatge es troben en contigs de longitud igual o superior a $L$ [70](#page=70). #### 3.1.2 Càlcul de N50 i N75 El càlcul del N50 i N75 segueix els passos següents [70](#page=70) [71](#page=71): 1. **Obtenir les longituds dels contigs:** Crear una llista amb la longitud de cada contig no buit de l'ensamblatge. 2. **Calcular la suma total de bases:** Sumar totes les longituds dels contigs per estimar la mida total del genoma. 3. **Ordenar les longituds:** Ordenar la llista de longituds de contigs de major a menor. 4. **Definir els llindars:** Calcular els llindars per al N50 (50% de la suma total de bases) i N75 (75% de la suma total de bases). Es fa ús de la funció sostre ($\lceil \dots \rceil$) per obtenir el valor enter més proper per a dalt [70](#page=70). * Llindar N50: $thr_{50} \leftarrow \lceil 0.50 \times T \rceil$, on $T$ és la suma total de bases. * Llindar N75: $thr_{75} \leftarrow \lceil 0.75 \times T \rceil$, on $T$ és la suma total de bases. 5. **Acumular longituds i trobar els contigs llindar:** Recórrer la llista de longituds ordenades, acumulant les longituds. El primer valor de longitud que fa que la suma acumulada superi $thr_{50}$ és el N50. De la mateixa manera, el primer valor de longitud que fa que la suma acumulada superi $thr_{75}$ és el N75. El procés es pot aturar un cop s'han definit tant N50 com N75 [71](#page=71). > **Tip:** Un N50 (o N75) més gran indica un ensamblatge més continu, ja que significa que hi ha menys contigs llargs necessaris per cobrir una gran proporció del genoma [69](#page=69). > **Example:** > Suposem un total de bases de 188.1 Mb [68](#page=68). > La meitat del total és $188.1 \text{ Mb} / 2 = 94.05 \text{ Mb}$ [68](#page=68). > Si, després d'ordenar els contigs, la suma acumulada de les longituds dels contigs més llargs arriba a 96.3 Mb quan es considera un contig de longitud 9.7 Mb, i aquest contig és el primer que fa que la suma acumulada superi 94.05 Mb, aleshores N50 = 9.7 Mb [68](#page=68). #### 3.1.3 Ensambladors conservadors vs. agressius L'elecció d'un ensamblador pot impactar en la qualitat de l'ensamblatge. * Un **ensamblador conservador** tendeix a produir pocs errors però molts contigs curts [72](#page=72). * Un **ensamblador agressiu** pot produir menys contigs llargs, però amb el risc de tenir més errors [72](#page=72). L'objectiu és trobar un equilibri per obtenir un resultat fiable i informatiu del genoma [72](#page=72). ### 3.2 Formats de fitxer en bioinformàtica Els formats de fitxer són crucials per emmagatzemar i intercanviar dades d'anàlisi genòmica. Dos formats destacats són FASTQ i SAM. #### 3.2.1 Format FASTQ El format FASTQ s'utilitza habitualment per emmagatzemar seqüències d'ADN o ARN juntament amb les seves puntuacions de qualitat associades. Cada entrada en un fitxer FASTQ consta de quatre línies [77](#page=77) [80](#page=80): 1. Línia que comença amb '@', seguida del nom de la seqüència i altra informació opcional [80](#page=80). 2. La seqüència nucleotídica (A, T, C, G) [80](#page=80). 3. Línia que comença amb '+', seguida opcionalment del nom de la seqüència [80](#page=80). 4. Les puntuacions de qualitat per a cada nucleòtid de la seqüència anterior, codificades usant ASCII. La longitud d'aquesta línia ha de ser idèntica a la de la seqüència [77](#page=77) [80](#page=80). > **Tip:** La qualitat de les seqüències pot ser més baixa en els cicles tardans de la seqüenciació, ja que hi ha més possibilitats de desincronització dels patrons de seqüenciació [77](#page=77). #### 3.2.2 Codificació de puntuacions de qualitat (Phred) Les puntuacions de qualitat (Q-scores) representen la probabilitat que un nucleòtid s'hagi identificat incorrectament. Per estalviar espai, aquestes puntuacions numèriques es converteixen a caràcters ASCII [82](#page=82). * **La codificació Phred:** Aquesta codificació relaciona un valor Q amb una probabilitat d'error. La fórmula general és: $Q = -10 \log_{10}(P_{error})$ on $P_{error}$ és la probabilitat d'un error en la identificació del nucleòtid [80](#page=80). * **Offset ASCII:** Diferents plataformes de seqüenciació utilitzen diferents "offsets" (desplaçaments) per mapejar els valors Q a caràcters ASCII [82](#page=82). * **Sanger/Illumina 1.8+:** Utilitza un offset de 33. Per tant, un caràcter ASCII $C$ es tradueix a un Q-score $Q$ mitjançant la fórmula $Q = \text{ASCII}(C) - 33$. Per exemple, el caràcter '!' (ASCII 33) correspon a un Q0, mentre que 'I' (ASCII 73) correspon a un Q40 [82](#page=82). * **Solexa/Illumina 1.0:** Utilitza un offset de 64, on $Q = \text{ASCII}(C) - 64$. > **Example:** > Si en la línia de qualitat d'un fitxer FASTQ apareix el caràcter '!', amb un offset de 33, el Q-score corresponent és $Q = 33 - 33 = 0$. Això indica una qualitat molt baixa per a aquest nucleòtid. Si apareix el caràcter 'I', el Q-score és $Q = 73 - 33 = 40$ indicant una qualitat excel·lent [82](#page=82). * **Rang de caràcters:** Els caràcters ASCII utilitzats per a les puntuacions de qualitat típicament van des de '!' (ASCII 33) fins a '~' (ASCII 126). Els caràcters de control no imprimibles (0-31) no s'utilitzen per a aquest propòsit [81](#page=81) [82](#page=82). #### 3.2.3 Format SAM (Sequence Alignment/Map) El format SAM és un format estàndard per emmagatzemar aligned sequence reads (lectures de seqüència alineades). Aquest format és més complex que FASTQ, ja que conté informació detallada sobre com una seqüència s'ha alineat a un genoma de referència [84](#page=84). * **Estructura:** Un fitxer SAM consta de dues seccions: una capçalera opcional que comença amb '@' i les línies de dades que descriuen els alineaments. Cada línia de dades conté 11 camps obligatoris i pot incloure camps opcionals [85](#page=85). * **Camps obligatoris:** Inclouen el nom de la consulta, flags, posició d'alineament, puntuació d'alineament, etc. * **Camps opcionals:** Poden contenir informació addicional sobre l'alineament, codificada com `TAG:TYPE:VALUE` [85](#page=85). * **FLAG:** Un camp clau en el format SAM és el "FLAG", que és un valor decimal que representa una combinació binària de diverses característiques de l'alineament. Cada bit del flag indica informació específica, com ara si la lectura està emparellada, si està en el cromosoma correcte, la direcció de la lectura, etc.. Hi ha 12 bits utilitzats per representar aquesta informació [86](#page=86) [87](#page=87). > **Tip:** Existeixen diverses eines web útils per interpretar el FLAG en els fitxers SAM, com ara les disponibles a `samformat.info` o `broadinstitute.github.io/picard` [86](#page=86) [87](#page=87). * **Format BAM:** sovint, els fitxers SAM s'ometen per a la compressió i s'utilitza el format BAM (Binary Alignment/Map), que és la versió binària i comprimida del format SAM [84](#page=84). --- # Flux de treball i eines en bioinformàtica Aquesta secció descriu el flux de treball estàndard per a l'anàlisi genòmica, des de les dades brutes de seqüenciament fins a la identificació de variants genètiques, detallant les eines clau i els conceptes d'optimització d'algoritmes [97](#page=97). ### 4.1 El flux de treball genòmic estàndard El procés d'anàlisi genòmica generalment comença amb les lectures brutes obtingudes del seqüenciament, normalment en format FASTQ. Aquestes lectures es mapegen posteriorment a un genoma de referència [97](#page=97). #### 4.1.1 Obtenció i processament de dades * **Lectures (FASTQ):** Són les seqüències d'ADN obtingudes del seqüenciament genòmic [97](#page=97). * **Control de qualitat i filtratge:** Eines com FastQC s'utilitzen per avaluar la qualitat de les lectures, i Trimmomatic s'encarrega de retallar o eliminar bases de baixa qualitat i adaptadors [97](#page=97). * **Mapeig (Alignment):** Les lectures processades es mapegen a un genoma de referència. Eines com BWA (Burrows-Wheeler Aligner) són habituals per a aquesta tasca. El resultat d'aquest pas sol ser un fitxer SAM (Sequence Alignment/Map) [97](#page=97). #### 4.1.2 Conversió i manipulació d'alineaments * **SAMtools view | sort:** SAMtools és una suite d'eines fonamentals per manipular fitxers SAM/BAM. El comandament `view` permet convertir entre formats (per exemple, SAM a BAM) i filtrar alineaments, mentre que `sort` ordena els alineaments, un pas necessari per a moltes operacions posteriors. El format BAM (Binary Alignment/Map) és una versió comprimida del format SAM, més eficient per a emmagatzematge i processament [97](#page=97). * **Picard:** Aquesta suite d'eines és essencial per a manipulacions avançades de fitxers BAM. Comandaments com `AddOrReplaceReadGroups` afegeixen o modifiquen metadades als alineaments, i `MergeSamFiles` combina múltiples fitxers BAM. Aquests passos són crucials per preparar les dades per a l'anàlisi de variants, especialment l'addició de `readgroup tags` [97](#page=97). * **BAMtools filter:** Permet realitzar filtratges més específics sobre els alineaments en format BAM [97](#page=97). #### 4.1.3 Identificació i anotació de variants * **Sequence variation (VCF):** L'objectiu final de moltes anàlisis genòmiques és identificar variacions en la seqüència respecte al genoma de referència. El format VCF (Variant Call Format) s'utilitza per registrar aquestes variants [97](#page=97). * **BCFtools mpileup:** Aquesta eina genera un fitxer `pileup` a partir d'alineaments BAM, que conté informació sobre les bases de cada posició del genoma [97](#page=97). * **BCFtools query:** Permet extreure informació específica del fitxer VCF generat, com ara consultar variants o estadístiques [97](#page=97). * **Annotated Variants:** Els variants identificats sovint s'anoten amb informació funcional, genètica o clínica per ajudar a la seva interpretació [97](#page=97). ### 4.2 Problemes de mapeig exacte i optimització d'algoritmes #### 4.2.1 Mapeig exacte naïf En un enfocament de mapeig exacte naïf, cada read es compara amb totes les possibles posicions del genoma de referència. * **Càlcul de possibles alineaments:** Si un genoma té una longitud de $y$ parells de bases (bp) i un read té una longitud de $x$ bp, el nombre de possibles alineaments naïfs és $y - x + 1$ [100](#page=100). * **Example:** Per al genoma del SARS-CoV-2 de 29,903 bp i reads d'Illumina de 150 bp, el nombre d'alineaments possibles per a cada read és $29,903 - 150 + 1 = 29,754$ [100](#page=100). * **Càlcul de comparacions de caràcters:** El nombre total de comparacions de caràcters necessàries per localitzar tots els possibles mapejos d'un read amb longitud $x$ en un genoma de referència de longitud $y$ és $(y - x + 1) \times x$ . * **Example:** Per al genoma del SARS-CoV-2 (29,903 bp) i reads de 150 bp, el nombre total de comparacions de caràcters és $29,754 \times 150 = 4,463,100$ . #### 4.2.2 Optimització d'algoritmes de mapeig L'estratègia naïf és computacionalment molt costosa, especialment amb genomes grans i moltes lectures. Per optimitzar el mapeig exacte, s'utilitzen algorismes més eficients. * **Algorismes optimitzats:** L'algorisme de **Boyer-Moore** és un exemple d'algorisme que pot utilitzar-se per optimitzar el mapeig exacte de reads contra un genoma de referència, ja que redueix el nombre de comparacions necessàries. Altres tècniques inclouen l'ús d'estructures de dades indexades com índexs de suffixos o taules de hashing . #### 4.2.3 Pre-processament per optimitzar el mapeig Per accelerar el procés de mapeig, es pot pre-processar tant el genoma de referència com els patrons (les lectures) . * **Pre-processament del genoma:** Indexar el genoma de referència amb algorismes com BWA permet realitzar cerques molt més ràpides [97](#page=97). * **Pre-processament de patrons (lectures):** Si bé no és tan comú com el pre-processament del genoma per al mapeig exacte, en algorismes més complexos es poden aplicar tècniques de filtratge o agrupació de lectures similars . > **Tip:** La comprensió dels formats de fitxer clau com FASTQ, SAM i BAM és fonamental per entendre el flux de treball i utilitzar eficaçment les eines de bioinformàtica [97](#page=97) [99](#page=99). > **Tip:** Els problemes de complexitat computacional en bioinformàtica sovint es resolen mitjançant l'elecció d'algoritmes eficients i l'ús d'estructures de dades optimitzades . --- ## Common mistakes to avoid - Review all topics thoroughly before exams - Pay attention to formulas and key definitions - Practice with examples provided in each section - Don't memorize without understanding the underlying concepts

| Term | Definition | |------|------------| | Ensamblatge de genoma | El procés de reconstruir una seqüència genòmica completa a partir de fragments de seqüència més petits (lectures) obtinguts mitjançant seqüenciament de nova generació. | | NP-complet | Una classe de problemes computacionals per als quals no es coneix cap algoritme eficient que els resolgui en temps polinomial, i que són tan difícils com qualsevol altre problema en la classe NP. | | Aproximació | Una estratègia per resoldre problemes computacionals difícils (sovint NP-complets) cercant solucions que estiguin properes a l'òptim, en lloc de garantir l'òptim absolut. | | Randomització | Una tècnica que utilitza nombres aleatoris com a part del seu algorisme per prendre decisions o per influir en la seva execució, sovint per millorar l'eficiència o la probabilitat d'èxit en problemes computacionals complexos. | | Parametrització | Una tècnica d'optimització d'algorismes que es basa en la transformació d'un problema en una família de problemes parametritzats, amb l'objectiu de trobar solucions eficients per a certs paràmetres. | | Heuristic search (Recerca heurística) | Un mètode d'optimització que busca solucions aproximades a problemes computacionals, especialment quan els problemes són massa complexos per trobar una solució exacta en un temps raonable. | | Graf de De Bruijn | Un graf dirigit utilitzat en bioinformàtica per a l'assemblatge de genoma, on els nodes representen k-mers (seqüències de longitud k) i les arestes connecten k-mers que difereixen en un sol nucleòtid per un extrem. | | Grafs d'overlap (solapes) | Un tipus de graf utilitzat en bioinformàtica on els nodes representen lectures individuals i les arestes indiquen que dues lectures comparteixen un solapament significatiu. | | N50 | Una mesura de la qualitat d'un ensamblatge genòmic. Representa la longitud mínima d'un contig tal que el 50% de les bases de l'ensamblatge total es troben en contigs de longitud igual o superior a N50. | | N75 | Similar a N50, però indica la longitud mínima d'un contig tal que el 75% de les bases de l'ensamblatge total es troben en contigs de longitud igual o superior a N75. | | FASTQ | Un format de fitxer de text utilitzat per emmagatzemar dades de seqüenciament biològic, incloent la seqüència d'ADN o ARN i les puntuacions de qualitat associades per a cada base. | | SAM (Sequence Alignment Map) | Un format de fitxer de text pla utilitzat per emmagatzemar dades d'alineament de seqüències. Cada línia representa una lectura alineada a una seqüència de referència. | | BAM (Binary Alignment Map) | La versió binària comprimida del format SAM, que és més eficient en termes d'espai i velocitat de processament. | | Quality Score (Puntuació de qualitat) | Un valor numèric associat a cada base en una seqüència de seqüenciament, que indica la probabilitat que la base s'hagi identificat incorrectament. S'expressa sovint en l'escala Phred. | | Codificació Phred | Un sistema per representar les puntuacions de qualitat de les bases de seqüenciament com a caràcters ASCII. La fórmula general és $Q = -\log_{10}(P)$, on $P$ és la probabilitat d'un error, i la puntuació ASCII s'obté sumant un valor d'offset a $Q$. | | Offset | Un valor constant utilitzat en la codificació Phred per convertir puntuacions de qualitat numèriques en caràcters ASCII. Diferents plataformes de seqüenciament utilitzen diferents offsets (per exemple, 33 per Sanger/Illumina 1.8+). | | FLAG (en SAM/BAM) | Un camp numèric en els fitxers SAM/BAM que codifica diverses característiques d'un alineament de lectura, com ara si la lectura està aparellada, si està en la cadena correcta, si és la primera o la segona de la parella, etc. | | Mapeig exacte | El procés d'identificar totes les posicions en una seqüència de referència on una seqüència més curta (una lectura) coincideix exactament sense cap error. | | Boyer-Moore | Un algorisme eficient per a la cerca de subcadenes que s'utilitza sovint en bioinformàtica per al mapeig de lectures contra genomes de referència, ja que pot accelerar significativament el procés de cerca. |