Correção de cordas usando a distância Damerau-Levenshtein | BMC Bioinformática

Algoritmos de núcleo único
O algoritmo de espaço linear L S_D L
O algoritmo de espaço linear S t r i p_D L
O algoritmo de traçado de espaço linear L S D L_T R A C E
O algoritmo de traçado de tira S t r i p_T R A C E
Multi-core algorithms
O algoritmo P P_D L
O algoritmo P P_L S_D L
O algoritmo P P_S t r i p_D L
O algoritmo P P_D L_T R A C E
Os algoritmos P P_L S D L_T R A C E e P_S t r i p_T R A C E

Algoritmos de núcleo único

Nesta seção, desenvolvemos quatro algoritmos de núcleo único de espaço linear para correção de cordas usando a distância DL. Todos os quatro correm no tempo O(mn). Os dois primeiros (LS_DL e Strip_DL) computam apenas a pontuação Hmn do traço óptimo; eles diferem na sua eficiência de cache. Os dois últimos (LSDL_TRACE e Strip_TRACE) calculam um traço óptimo.

O algoritmo de espaço linear L S_D L

Deixe s ser do tamanho do alfabeto. Ao invés de usar o array H usado em DL, o algoritmo LS_DL usa um array unidimensional U e um array bidimensional T. Estes dois array têm um espaço requerido de O((s+1)n) = O(n) para constantes s. Quando m<n, pode-se trocar A e B para reduzir a memória requerida. Adicionando a memória necessária para A e B, a complexidade do espaço é O(s min{m,n}+m+n) = O(m+n) quando s é uma constante.

As no algoritmo DL, os valores de Hij são computados por linhas. O array unidimensional U é usado para salvar os valores H computados pelo algoritmo DL quando a linha i está sendo computada. Deixe H ser a última linha computada para o caractere c. Então, T é a linha w-1 do algoritmo H. O algoritmo 2 dá o pseudo-código para LS_DL. Sua exatidão segue da exatidão do algoritmo DL. Note que swap(T],U) leva o tempo O(1) como ponteiros para 2 arrays unidimensionais são trocados ao invés do conteúdo desses arrays. A contagem de cache-miss para LS_DL é a mesma que para DL quando n é suficientemente grande, pois ambos têm o mesmo padrão de acesso aos dados. No entanto, para instâncias menores o LS_DL exibirá um comportamento de cache muito melhor. Por exemplo, devido ao seu uso de muito menos memória, podemos ter cache LLC suficiente para armazenar todos os dados em LS_DL mas não em DL (O(sn) vs O(mn)).

O algoritmo de espaço linear S t r i p_D L

Quando (s+1)n é maior que o tamanho do cache LLC, podemos reduzir as falhas de cache em relação ao algoritmo LS_DL calculando Hij por tiras de largura q, para algumas q menos que n (a última tira pode ter uma largura menor que q). Isto é mostrado na Fig. 3. As tiras são computadas na ordem 0, 1,… usando o algoritmo LS_DL. No entanto, o espaço necessário por T e U no LS_DL é reduzido para (s+1)q uma vez que a largura da tira é q em vez de n. Escolhendo q suficientemente pequeno, podemos assegurar que os blocos dos conjuntos T e U utilizados pelo LS_DL não são despejados da cache uma vez que são trazidos. Assim, se cada entrada de T e U leva 1 palavra, então quando o tamanho da cache é lw, temos q<lw/(s+1). Note que, para além de T e U, a cache precisa de manter partiais de A, B e outras arrays necessárias para passar os dados de uma tira para a seguinte.

Para passar os dados de uma tira para a próxima, usamos uma tira adicional de array unidimensional de tamanho m e um array bidimensional s∗m V. A tira de array registra os valores de H computados para a coluna mais à direita na tira. V dá o valor de H na coluna mais à direita j da linha i de H que é (a) em uma tira à esquerda da que está sendo calculada atualmente e (b) c=B.

O pseudo-código para Strip_DL é dado no Algoritmo 3. Para maior clareza, este pseudo-código usa duas matrizes de tiras (linhas 18 e 30) e duas matrizes em V (linhas 24 e 32). Um conjunto de arrays é usado para buscar dados calculados para a tira anterior e o outro conjunto para os dados que serão passados para a tira seguinte. Na implementação real, usamos um único array de strip e um único array V sobrescrevendo valores recebidos do strip anterior com valores a serem passados para o próximo strip.

O tempo e complexidade do Strip_DL são, respectivamente, O(mn) e O((s+1)m+(s+1)q+n) = O(sm+sq+n) = O(sm+n) = O(sm+n) como q é uma constante. Quando m>n, podemos mudar A e B para conservar memória e assim a complexidade do espaço torna-se O(s min{m,n}+m+n) = O(m+n) para constante s.

Quando analisamos a falta de cache, notamos que q é escolhido de tal forma que U e T cabem na cache. Nós fazemos a suposição razoável de que a regra de substituição da LRU não causa qualquer bloco de U ou T a ser despejado durante a execução do algoritmo Strip_DL. Como resultado, o número total de falhas de cache devido a U e T é independente de m e n e por isso pode ser ignorado na análise. A inicialização da tira e V resulta em m/w e (s+1)m/w acessos lidos, respectivamente. O número de acessos de escrita é aproximadamente o mesmo que o número de acessos de leitura. O cálculo para cada faixa acessa a faixa de matriz em ordem ascendente de índice. Isto resulta em (aproximadamente) o mesmo número de falhas de cache que foi feito durante a fase de inicialização. Portanto, o número total de falhas de cache devido à tira é aproximadamente (2m/w)(n/q+1). Para V, notamos que ao calcular a tira atual, os elementos em qualquer linha de V são acessados em ordem não decrescente de índice (ou seja, da esquerda para a direita) e que precisamos reter, em cache, apenas o valor lido mais recentemente para cada caractere do alfabeto (ou seja, no máximo, os valores s devem ser retidos). Assumindo que um valor V é despejado do cache apenas quando um novo valor para o mesmo caracter é acessado, o número total de erros de leitura do V quando se computa uma única faixa é sm/w. O número de erros de escrita é aproximadamente o mesmo. Portanto, V contribui (2sm/w)(n/q+1). Assim, o número total de falhas de cache para o algoritmo Strip_DL é ≈2(s+1)mn/(wq) quando m e n são grandes.

Recordar que a contagem aproximada de falhas de cache para algoritmos DL e LS_DL é mn(1+3/w). Isto é (wq+3q)/(2s+2) vezes que para Strip_DL.

O algoritmo de traçado de espaço linear L S D L_T R A C E

Al embora os algoritmos LS_DL e Strip_DL determinem a pontuação (custo) de um traço óptimo (e portanto de uma sequência de edição óptima) que transforma A em B, estes algoritmos não guardam informação suficiente para determinar realmente um traço óptimo. Para determinar um traço óptimo utilizando o espaço linear, adoptamos uma estratégia de dividir e conquistar semelhante à utilizada por Hirschberg para o problema simples de edição de strings (ou seja, não são permitidas transposições) e Myers e Miller para o problema de alinhamento de sequências.

Dizemos que um traço tem um cruzamento central sef contém duas linhas (u1,v1) e (u2,v2), u1<u2 tal que v1>n/2 e v2≤n/2 (Fig. 4).

Deixe T ser um traço óptimo que satisfaça as propriedades P2-P4. Se T não contém cruzamento central, então suas linhas podem ser divididas em conjuntos TL e TR de tal forma que TL contenha todas as linhas (u,v)∈T com v≤n/2 e TR contém as linhas restantes (Fig. 4a). Como não há cruzamento de centros, todas as linhas em TR têm um valor u maior do que o valor u de cada linha em TL. Das propriedades P2-P4 decorre que existe um i, 1≤i≤m de tal forma que T é a união de um traço óptimo para A e B e que para A e B. Deixe H ser o custo do primeiro traço óptimo e H′ o do último traço óptimo. Vemos que quando T não tem cruzamento central, o custo de T é

$$ costNoCC(T) = \min_{1 \i}{ H + H’\i} $$

(3)

Quando T contém um cruzamento central, suas linhas podem ser particionadas em 3 conjuntos, TL, TM e TR, como mostrado na Fig. 4b. Deixe (u1,v1) e (u2,v2) serem as linhas que definem a passagem do centro. Note que TL contém todas as linhas de T com v<v2, TR contém todas as linhas com v>v1, e TM={(u1,v1),(u2,v2)}. Note também que todas as linhas na TL têm u<u1 e todas na TR têm u>u2. Da propriedade P1, segue-se que TL é um traço ótimo para A e B e TR é um traço ótimo para A e B. Além disso, como (u1,v1) e (u2,v2) são linhas balanceadas, o custo da TM é (u2-u1-1)+1+(v1-v2-1). Além disso, A≠A como de outra forma, a substituição das linhas de cruzamento central por (u1,v2) e (u2,v1) resulta em um traço de custo mais baixo. Da propriedade P4, sabemos que (u_{1}{\i} = lastA=phantom {\i}} e (v_{2} = lastB=phantom {\i}{\i}}. Que H seja o custo de um traço óptimo para A e B e que H′ seja o custo de um traço óptimo para A e B. Então, quando T tem um cruzamento central, o seu custo é

$$ {\begin{\begin{\begin{\begin} costCC(T) \,=\,& \min\{H + H’ \\ &+ (u_{2}-u_{1}-1) + 1 + (v_{1}-v_{2}-1)} \Fim de alinhamento $$

(4)

onde, para o min{}, tentamos 1≤u1<m e para cada um desses u1, definimos v1 como sendo o menor i>n/2 para o qual $b_{i} = a_{u_{1}}phantom {\i}{\i}!}$. Para cada u1, examinamos todos os caracteres, excepto o alfabeto. Para cada um desses caracteres c, v2 é definido para o maior j≤n/2 para o qual bj=c e u2 é o menor i>u1 para o qual ai=c. Assim, o min é assumido (s-1)m termos.

Let Utop e Ttop são as arrays U e T finais calculadas por LS_DL com entradas B e A e Ubot e Tbot são estas arrays quando as entradas são o inverso de B e A. A partir destas arrays, podemos determinar prontamente os valores H e H′ necessários para avaliar Eqs. 3 e 4. Algoritmo LSDL_TRACE (Algoritmo 4) fornece o pseudo-código para o nosso cálculo do espaço linear de um traço ótimo. Ele assume que o LS_DL foi modificado para retornar ambos os arrays U e T.

Para a complexidade temporal, vemos que no nível superior da recursividade, invocamos o LS_DL duas vezes com as cadeias A e B de tamanho m e n/2, respectivamente. Isto leva no máximo amn time para alguma constante a. O tempo necessário para calcular Eqs. 3 e 4 é O(sn) e pode ser absorvido pelo amn usando uma constante a. No próximo nível de recursividade, LS_DL é invocado 4 vezes. A soma dos comprimentos das cadeias A através destas 4 invocações é no máximo 2m e a cadeia B tem comprimento no máximo n/4. Portanto, o tempo para estas quatro invocações é, no máximo, amn/2. Generalizando para os níveis restantes de recursividade, vemos que o algoritmo LSDL_TRACE leva amn(1+1/2+1/4+1/8+…)<2amn=O(mn) time. O espaço necessário é o mesmo que o do LS_DL (note que os parâmetros para este algoritmo foram trocados). Da análise de tempo, segue-se que o número de falhas de cache é aproximadamente o dobro do que para LS_DL quando invocado com strings de tamanho m e n. Assim, a contagem aproximada de falhas de cache para LSDL_TRACE é 2mn(1+3/w).

Notemos que alguma redução no tempo real de execução pode ser alcançada com a comutação de A e B quando A é menor que B, assegurando assim que a string mais curta é dividida em cada nível de recursividade. Isto permite-nos obter a terminação da recursividade mais rapidamente.

O algoritmo de traçado de tira S t r i p_T R A C E

Este algoritmo difere do LSDL_TRACE na medida em que utiliza uma versão modificada do Strip_DL em vez de uma versão modificada do LS_DL. A versão modificada da Strip_DL retorna as arrays strip e V computadas pela Strip_DL. Correspondentemente, Strip_TRACE usa Vtop e Vbot no lugar de Ttop e Tbot. A complexidade temporal assimptótica de Strip_TRACE também é O(mn) e ocupa a mesma quantidade de espaço que Strip_DL (note que os parâmetros para Strip_DL são trocados em relação àqueles para Strip_TRACE). O número de falhas de cache é aproximadamente o dobro do que para Strip_DL.

Multi-core algorithms

Nesta seção, descrevemos nossas paralelizações do algoritmo DL e os quatro algoritmos single-core da seção anterior. Essas paralelizações assumem que o número de processadores é pequeno em relação ao comprimento da string. A convenção de nomes que adotamos para as versões paralelas é adicionar PP_ como prefixo ao nome do algoritmo de núcleo único.

O algoritmo P P_D L

A nossa versão paralela do algoritmo DL, PP_DL, calcula os elementos na mesma ordem que o DL. Entretanto, ele inicia o cálculo de uma linha antes que o cálculo da sua linha anterior esteja completo. A cada processador é atribuída uma única linha a calcular e ele computa esta linha da esquerda para a direita. Deixe p ser o número de processadores. O processador z é inicialmente atribuído para fazer o cálculo do loop externo para i=z, 1≤i≤p. O processador z começa após um intervalo de tempo adequado em relação ao início do processador z-1 para que os dados necessários para seu cálculo já tenham sido computados pelo processador z-1. No nosso código, o intervalo de tempo entre o início do cálculo de duas filas consecutivas é o tempo necessário para calcular os elementos n/p. Após a conclusão do seu cálculo da iteração i, o processador procede à iteração i+p do laço externo. A complexidade temporal do PP_DL é O(mn/p).

O algoritmo P P_L S_D L

Embora a estratégia geral de paralelização do PP_LS_DL seja a mesma que a utilizada no PP_DL, é necessário um cuidado extra para assegurar um cálculo idêntico ao do LS_DL. A divergência nos resultados é possível quando dois ou mais processadores estão simultaneamente a computar diferentes linhas de H usando a mesma memória. Isto acontece, por exemplo, quando A=aaabc⋯ e p≥3. Começamos com o processador i atribuído para calcular a linha i de H, 1≤i≤p. Suponha que U=x e T=y inicialmente (note que x e y são endereços na memória). Devido à declaração swap(T],U) em LS_DL, o processador 1 começa a calcular a linha 1 de H usando memória começando no endereço y. Se o processador 2 começar com um intervalo de tempo adequado como em PP_DL, ele irá calcular a linha 2 de H usando memória começando no endereço x. Com um atraso adicional, o processador 3 começará a computar a linha 3 de H novamente usando a memória começando no endereço y. Agora, ambos os processadores 1 e 3 estão usando a mesma memória para computar linhas diferentes de H e assim corremos o risco de sobrescrever os valores de H que podem ser necessários para cálculos subsequentes. Como outro exemplo, considere A=ababa⋯ e p≥4. Suponha que U=x e T= inicialmente. O processador 1 começa a computar a linha 1 usando a memória y, depois, com um atraso, o processador 2 começa a computar a linha 2 usando a memória z, depois o processador 3 começa a computar a linha 3 usando a memória x. O próximo processador 4 começa a computar a linha 4 usando a memória y. Neste momento o processador 1 está a calcular a linha 1 com A=a e o processador 4 está a calcular a linha 4 com A=b e ambos os processadores estão a usar a mesma linha de memória y.

Deixe que p1 e p2 sejam dois processadores que estão a usar a mesma memória para calcular linhas r1<r2 de H e que nenhum processador está a usar esta memória para calcular uma linha entre r1 e r2. A partir do esquema de atribuição de troca usado em LS_DL, segue-se que p1 está a calcular a linha { r_{1} = lastA-1\phantom {\i}{i}}. Os valores H nesta linha são necessários para calcular as linhas r1+1 até r2 como “ponto” (phantom)!r_{1} = lastA r_{1} = lastA r_{1} < i {2}le r_{2}). Estes valores não são necessários para as linhas i>r2 como para estas linhas {\i}({\i}!{\i}lastA = r_{2} > r_{1} + 1 = LastA\). Deixe o J1 ser tal que… (phantom {\i}{\i}b_{j} = a_{r_{2}} = a_{r_{1} + 1}}). Então, para j>j1, {\i}({\i}phantom {\i}!{\i}lastB {\i}ge j_{\i}). Assim, para j>j1 colunas 1 até j1-2 da linha r1 não são necessárias para calcular um H nas linhas entre r1 e r2.

O nosso código paralelo utiliza um esquema de sincronização que se baseia nas observações do parágrafo anterior para atrasar a sobreposição dos valores necessários para cálculos posteriores e assegurar um cálculo correcto da distância DL. Nosso esquema de sincronização emprega outro array W que é inicializado em 1. Suponha que um processador esteja calculando a linha i de H e que A=a. Quando este processador encontra um a em B, digamos na posição j1, ele incrementa W. Quando o próximo a é encontrado, digamos em j2, ele incrementa W em 1. Quando o processador termina seu cálculo da linha i, as posições restantes de W são incrementadas em 1. O processador designado para calcular a linha q de H pode calcular U sef W=q. A partir de nossas observações anteriores, segue-se que quando W=q, os valores antigos nas posições de memória U podem ser sobregravados, pois estes não são necessários para cálculos futuros.

Este algoritmo de tempo do processador p PP_LS_DL depende dos conjuntos de dados, pois o atraso de sincronização é dependente dos dados. Nós, entretanto, esperamos um desempenho em tempo de execução de aproximadamente O(mn/p) quando os caracteres em B são distribuídos de forma mais ou menos uniforme.

O algoritmo P P_S t r i p_D L

Na versão paralela PP_Strip_DL da Strip_DL, o processador i é inicialmente atribuído ao cálculo da strip i, 1≤i≤p. Após a conclusão de sua tira j atualmente atribuída, o processador procede para computar a tira j+p. Um sinal de array é usado para fins de sincronização. Ao calcular uma linha r na sua tira s atribuída, o processador precisa esperar até que o sinal=s. sinal seja ajustado para s pelo processador que trabalha na tira s-1 quando os valores à esquerda da tira s necessários no cálculo da linha r da tira s tiverem sido calculados e não há risco de que os cálculos para a linha r da tira s sobrescrevam os valores V necessários por outros processadores. sinal funciona muito parecido com W em PP_LS_DL.

Nota que quando estamos trabalhando em tiras p, precisamos de cópias p dos arrays U e T usados por Strip_DL.

A complexidade temporal da PP_Strip_DL depende do atraso de sincronização e espera-se que O(mn/p).

O algoritmo P P_D L_T R A C E

Este algoritmo primeiro usa PP_DL para calcular H. Depois, um único processador executa um traceback para construir o traceback ótimo. Para valores razoáveis de p, o tempo de execução é dominado pelo PP_DL e assim, a complexidade do PP_DL_TRACE é também O(mn/p).

Os algoritmos P P_L S D L_T R A C E e P_S t r i p_T R A C E

No LSDL_TRACE (Strip_TRACE), dividimos repetidamente o problema em dois e aplicamos ou LS_DL (Strip_DL) a cada partição. A versão paralela PP_LSDL_TRACE (PP_Strip_TRACE) emprega a seguinte estratégia de paralelização:

Cada subproblema é resolvido usando PP_LS_DL (PP_Strip_DL) quando o número de subproblemas independentes é pequeno; todos os processadores p são atribuídos à solução paralela de um único subproblema. Isto é, os subproblemas são resolvidos em seqüência.
p subproblemas são resolvidos em paralelo usando LS_DL (Strip_DL) para resolver cada subproblema em série quando o número de subproblemas independentes é grande,

A complexidade temporal de PP_LSDL_TRACE e PP_Strip_TRACE é O(mn/p).