Introducció

Aquesta aplicació pressuposa que el usuari ja disposa d'uns certs coneixements bàsics sobre l'ADN i el seu comportament, un cop complert aquest requisit podem passar a explicar en què consisteix aquesta aplicació.

El mètode de seqüenciació per Shotgun es bastant coneguda a l'actualitat, el procés en termes generals consisteix en primer replicar el fragment d'ADN a seqüenciar, fragmentar de forma aleatòria les seqüències replicades (mètode Shotgun) i un cop fet aixó intentar recomposar la seqüència a partir dels fragments solapats. Aquesta última etapa es amb molt la més complicada de les tres, si bé els errors que es puguin produir a les altres dos etapes prèvies son una complicació afegida.

Bé, el problema que ens ocupa es el següent: quan volem recompossar la seqüència original a partir dels fragments, hem de comparar cada par de segments per conèixer la millor superposició possible entre tots dos o si no es solapen en absolut. Si has de comparar cada par de segments, el nombre de comparacions té una cota màxima de O(n^2) (on n es el nombre de segments), això ha de multiplicar-se pel cost de cada comparació. L'algoritme que retorna el solapament òptim té un cost aproximat de O(m^2) (on m es el nombre de bases del fragment), així obtenim que el cost del procés de comparació de segments té un cost de O(n^2) * O(m^2), si considerem que el nombre de bases dels fragments es semblant al de segments, obtindrem un cost aproximat de O(n^4), aquest cost no es acceptable computacionalment si tractem amb una n de magnitud superior al miler.

Com hem vist, el cost computacional d'aquest procés es inadmissible, per això s'intenta abordar el problema d'una altra manera: en comptes d'aplicar l’algoritme quadràtic de força bruta, primer apliquem un algoritme de criba a cada par, així, ens quedarem només amb els parells de bases candidates, aquells als que sigui possible trobar una superposició; així, el conjunt inicial de comparacions es veurà reduït en un ordre de magnitud. El cost d'aquest procés serà de O(n^2) * O(m) = O(n^3) (suposant m i n amb magnitud similar), que es a diferència del cost de l'algoritme anterior, computable.

Aquest programa didàctic tractarà d'explicar el funcionament de l'algoritme de criba. Aquest algoritme es basa en la cerca de grups de bases coincidents, la longitud mínima d'aquests grups be donada per l'usuari. Així les entrades de l'algoritme seran els dos segments d'ADN i un paràmetre numèric que indicarà la sensibilitat del procés.