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.