Aproximado de la cadena de algoritmos a juego

Question

Aquí en el trabajo, a menudo necesitamos encontrar una cadena a partir de la lista de cadenas que es el más parecido al de algunos otros de la cadena de entrada.Actualmente, estamos utilizando Needleman-Wunsch algoritmo.El algoritmo vuelve a menudo una gran cantidad de falsos positivos (si se establece el mínimo de puntuación demasiado baja), a veces no se encuentra una coincidencia, cuando debería (cuando el mínimo de puntuación es demasiado alta) y, la mayoría de las veces, tenemos que comprobar los resultados con la mano.Pensamos que debe probar otras alternativas.

¿Tienes alguna experiencia con los algoritmos?¿Sabe usted cómo los algoritmos a comparar a uno con el otro?

Agradecería algún consejo.

PS:Estamos codificación en C#, pero no se preocupan por ella - estoy preguntando acerca de los algoritmos en general.

---

Oh, lo siento, se me olvidó mencionar que.

No, no lo estamos utilizando para que coincida con los datos duplicados.Tenemos una lista de cadenas que estamos buscando - le llamamos de búsqueda de la lista.Y entonces necesitamos para procesar textos procedentes de diversas fuentes (como los canales RSS, sitios web, foros, etc.) - podemos extraer partes de los textos (hay toda una serie de reglas para que, pero eso es irrelevante) y tenemos que coincidir en contra de la búsqueda de la lista.Si la cadena coincide con una de las cadenas de la búsqueda-lista - tenemos que hacer algo de procesamiento de la cosa (que también es irrelevante).

No podemos realizar la normal de comparación, debido a que las cadenas de caracteres extraídos de las fuentes externas, la mayoría de las veces, se incluyen algunas palabras adicionales, etc.

De todos modos, no es para la detección de duplicados.

Answer 1

OK, Needleman-Wunsch(NW) es un clásico de extremo a extremo ("global") alineador de la literatura la bioinformática.Fue hace mucho tiempo disponible como "alinear" y "align0" en la FASTA paquete.La diferencia fue que el "0" de la versión no era tan sesgada acerca de evitar el final de distanciamiento, que a menudo se les permite favoreciendo de alta calidad interno de los partidos más fácil.Smith-Waterman, sospecho que eres consciente, es un local de alineador y es la base original de la EXPLOSIÓN.FASTA tenía su propio local alineador así que fue un poco diferente.Todos estos son esencialmente heurística métodos para la estimación de la distancia de Levenshtein correspondiente a un puntaje métrica de carácter individual pares (en bioinformática, a menudo se da por Dayhoff/"PAM", Henikoff&Henikoff, o de otras matrices, y generalmente se reemplaza con algo más simple y más que un reflejo de reemplazos en lingüística de la morfología de la palabra cuando se aplica al lenguaje natural).

No vamos a ser preciosos acerca de las etiquetas:Distancia de Levenshtein, como se hace referencia en la práctica al menos, es básicamente de distancia de edición y usted tiene que calcular porque no es posible calcular en general, y es caro para calcular exactamente incluso en interesantes casos especiales:el agua es profunda rápido de allí, y por lo tanto tenemos heurística métodos de largo y de buena reputación.

Ahora, en cuanto a su propio problema:hace varios años, tuve que comprobar la exactitud de cortos de ADN, se lee en contra de la secuencia de referencia conocida para ser la correcta y se me ocurrió algo que me llama "anclado alineaciones".

La idea es tomar su cadena de referencia y "digerir" es mediante la búsqueda de todos los lugares en los que un determinado N-carácter de la subcadena se produce.Elegir N de modo que la tabla que construir no es demasiado grande, pero también para que las subcadenas de longitud N no son demasiado comunes.Para los pequeños alfabetos como bases de ADN, es posible llegar a un perfecto hash en las cadenas de N caracteres y hacer una tabla y la cadena de los partidos en una lista enlazada de cada bin.Las entradas de la lista debe identificar la secuencia y posición de inicio de la subcadena que se asigna a la bandeja, en cuya lista se producen.Estas son las "anclas" en la lista de cadenas de caracteres para ser buscado en el que una alineación NW es probable que sea útil.

Cuando el procesamiento de una cadena de consulta, se toma la N caracteres a partir de algunos desplazamiento de K en la cadena de consulta, croquetas de ellos, buscar sus bin, y si la lista para que la papelera está vacía después de ir a través de toda la lista de registros y realizar las alineaciones entre la cadena de consulta y la cadena de búsqueda que se hace referencia en el registro.Al hacer estas alineaciones, de que la línea de la cadena de consulta y la cadena de búsqueda en el ancla y extraer una subcadena de la cadena de búsqueda que es la misma longitud que la cadena de consulta, y que contiene que ancla en el mismo desplazamiento, K.

Si usted elige un tiempo suficiente de anclaje longitud N, y un conjunto razonable de los valores de desplazamiento de K (que se puede propagar a través de la cadena de consulta o restringido a baja offsets) usted debe obtener un subconjunto de posibles alineaciones y, a menudo obtendrá más claros ganadores.Normalmente se desea utilizar la final menos sesgada align0-como NW alineador.

Este método intenta potenciar NW un poco por la restricción es de entrada, y esto tiene una ganancia de rendimiento debido a que hace menos de alineaciones y son más a menudo entre las secuencias similares.Otra buena cosa que hacer con su NW aligner es permitir a renunciar después de una cierta cantidad o longitud de distanciamiento se produce para reducir los costos, especialmente si usted sabe que no va a ver o estar interesado en cuanto a la mediocre calidad de los partidos.

Finalmente, este método fue utilizado en un sistema con pequeñas letras del alfabeto, con K restringido a las primeras 100 posiciones en la cadena de consulta y con cadenas de búsqueda mucho más grandes que las consultas (el ADN lecturas fueron alrededor de 1000 bases y las cadenas de búsqueda fueron del orden de 10000, por lo que yo estaba buscando aproximado subcadena partidos justificado por una estimación de la distancia de edición específicamente).La adaptación de esta metodología a lenguaje natural requerirá una cuidadosa reflexión:se pierde en el alfabeto de tamaño, pero usted gana si su consulta cadenas y cadenas de búsqueda son de la misma longitud.

De cualquier manera, permitiendo a más de uno de anclaje de los extremos diferentes de la cadena de consulta para ser utilizados al mismo tiempo podría ser útil en un posterior filtrado de datos se alimenta a NW.Si usted hace esto, estar dispuesta a enviar la superposición de las cadenas que contienen cada uno de los dos anclajes para el alineador y, a continuación, conciliar las alineaciones...o, posiblemente, modificar NW destacar mantener su anclajes casi intacta durante una alineación mediante la pena de modificación durante el algoritmo de ejecución.

Espero que esto sea útil o al menos interesante.

Answer 2

Relacionados con la Levenstein distancia:usted podría normalizar es dividiendo el resultado con la longitud de la cadena más larga, de modo que usted siempre obtener un número entre 0 y 1, y así poder comparar la distancia de un par de cadenas en una forma significativa (la expresión L(a, B) > L(a, C) - por ejemplo - no tiene sentido a menos que normalizar la distancia).

Answer 3

Alternativa a los algoritmos para mirar son agrep (Entrada de la Wikipedia en agrep), FASTA y la EXPLOSIÓN de biológicas de la secuencia de algoritmos a juego.Estos son casos especiales de aproximada de la cadena coincidente, también en el Stony Brook algoritmo repositry.Si usted puede especificar las formas en que las cadenas difieren de uno a otro, usted probablemente podría centrarse en una medida algoritmo.Por ejemplo, aspell utiliza alguna variante de "soundslike" (soundex-metaphone) distancia en combinación con un "teclado" distancia de acomodar a la mala abecedarios y mala typers por igual.

Answer 4

Estamos utilizando el Distancia de Levenshtein método de comprobación de duplicados de los clientes en nuestra base de datos.Funciona bastante bien.

Answer 5

Uso FM Índice con marcha atrás, similar a la que en Bowtie fuzzy alineador

Answer 6

Con el fin de minimizar los desajustes debido a pequeñas variaciones o errores de ortografía, he usado el Metaphone algoritmo, entonces la distancia de Levenshtein (en escala de 0 a 100 como un porcentaje de coincidencia) en el Metaphone codificaciones de una medida de proximidad.Que parece haber funcionado bastante bien.

Answer 7

Para ampliar en Cd-respuesta del Hombre, suena como que usted está frente a una normalización problema.No es obvio cómo manejar las puntuaciones entre alineaciones con diferentes longitudes.

Teniendo en cuenta lo que le interesa, puede que desee obtener los valores de p para su alineación.Si usted está usando Needleman-Wunsch, usted puede obtener los valores de p mediante Karlin-Altschul estadísticas http://www.ncbi.nlm.nih.gov/BLAST/tutorial/Altschul-1.html

La EXPLOSIÓN se puede alineación local y evaluar el uso de estas estadísticas.Si usted está preocupado acerca de la velocidad, esta sería una buena herramienta a utilizar.

Otra opción es utilizar HMMER.HMMER utiliza el Perfil de Modelos Ocultos de Markov para alinear secuencias.Personalmente, creo que esta es una más potente, ya que también proporciona información de posición. http://hmmer.janelia.org/

Answer 8

Yo solía trabajar con algunos de los más sucios que los datos que usted encontrará nunca.Un promedio de alrededor de 5000 filas de datos (equivalente a cientos de miles de dólares) requiere la coincidencia estaba totalmente agotado.Mi primera experiencia con la coincidencia aproximada fue de un algoritmo de Mr Excel escrito en VBA.Tenía ciertos problemas con la consistencia en que las cosas me esperaba a ser cero por ciento no estaban tha y las cosas que fueron cerca de 60 por ciento se parecía más a un 90 por ciento.Así que se trasladó a Levenshtein y luego Damerau-Levenshtein.Esto fue una mejora importante, pero bastante lento en Excel.A continuación, he saltado a Jaro-Winkler, pero rápidamente cayó poco después.Finalmente, en el año 2016 escribí mi propio (basado en n-gramas) y refinado en los próximos 2 años.Hoy es un add-on llamado Flookup;usted puede conseguir en Hojas de cálculo de Google y ver cómo se sostiene.