Óscar Miguel Rivera Borroto & col.
550
criterios para reducir el número de cálculos necesarios, incluyendo la proyección
de las instancias
d
-‐dimensionales en un espacio de dimensión menor, de forma tal
que varias instancias puedan ser buscadas, o eliminadas desde una búsqueda,
simultáneamente (108). En este sentido, varios de los algoritmos reportados
pueden no ser directamente aplicables a la búsqueda de los mejores pares en
contextos químicos ya que los primeros asumen que los atributos son variables
continuas, mientras que las estructuras químicas son descritas frecuentemente por
fragmentos de ocurrencia binaria. En estos casos, cada una de las estructuras en un
archivo se representa por una cadena de bits en el que se establece el bit
i-‐ésimo
si
el fragmento correspondiente está presente en la estructura. Además, a menudo se
supone que las instancias se encuentran en un espacio de dimensión
d
pequeña,
por lo general 2 o 3; sin embargo, para el caso de la representación química
binaria,
d
puede ser del orden de 10
2
o 10
3
(el número de bits en la cadena de bits),
y por ende estos algoritmos resultan ser poco factibles. Por ejemplo, el
procedimiento
O(nlog N)
debido a Friedman et al. (1977) implica una constante de
proporcionalidad alrededor de 1.6
d
(107), mientras que el método de búsqueda de
Bentley et a1. (1980) implica la inspección de todas las 3
d
-‐ 1 celdas adyacentes a
una celda dada en un espacio
d
-‐dimensional (108).
Alternativamente, otros investigadores han centrado su atención en los
algoritmos de búsqueda basados en la representación binaria. Smeaton y Van
Rijsbergen (1981) tienen en cuenta que un
archivo invertido
puede ser utilizado
para aumentar la eficiencia de la búsqueda de emparejamiento a una consulta en
documentos donde tiene al menos un término en común. A partir de aquí, estos
autores describen experimentos usando un procedimiento de
límite superior
que
permite que la búsqueda de la mejor pareja se termine antes de que todos los
documentos en la lista de los ficheros invertidos correspondientes a la consulta
hayan sido inspeccionados (109). Murtagh (1982) describe una extensión de este
algoritmo en el que son calculados otros límites superiores, posibilitando una
mayor reducción en el número de documentos que necesitan ser comparados con
una consulta (110).
Van Marlen y Van den Hende (1979), y Rasmussen et al. (1979) han descrito
algoritmos de recuperación de las mejores parejas para el uso de ficheros
informáticos con espectros de masa, donde la estructura es caracterizada por una
cadena de bits correspondientes a los picos observados en el espectro de masa
molecular (111, 112), mientras que otros autores han estudiado la búsqueda del
mejor emparejamiento en los sistemas de recuperación de información molecular
(106). Baldi et al. (2008) plantean un algoritmo diferente a los demás, el cual
consiste en almacenar para cada molécula A de la base de datos, no solamente su
vector correspondiente sino también almacenar información adicional contenida
