Par de alinhamento de sequências nucleotídicas usando o máximo de correspondências exatas
Abordagem
Nas nossas algoritmo proposto, o primeiro passo para o alinhamento de sequências é extrair MEMs entre sequências por comparação directa entre eles. A figura 3a é um exemplo que compara um alvo e uma sequência de consultas em que o CTC e o AAA são dois MEMs identificados pela comparação. Cada grupo de símbolos idênticos contínuos na comparação, resulta em um MEM mesmo que seja composto de apenas um único símbolo correspondente., A fim de extrair todos os MEMs entre as sequências, a sequência de consulta deve ser deslocada todo o caminho para a direita e para a esquerda um símbolo de cada vez(ver Fig. 3b). Após cada turno, o passo de comparação deve ser repetido para identificar novos MEMs. Por exemplo, a terceira linha na Fig. 3b representa o caso em que a sequência de consulta é deslocada para o símbolo um direito e é comparado com a sequência alvo. O resultado da comparação identifica a AAAAGC como uma nova MEM. Todos os outros MEMs extraídos por shift e operações de comparação também são destacados na Fig. 3b., Três das MEMs (MX,My e Mz) são destacadas com cores diferentes para serem usadas para explicações posteriores.
MEM extraction using shift and compare operations. a Identify MEMs by direct comparison of sequences. b a consulta é deslocada para a esquerda até que o último símbolo na sequência de consulta é alinhado com o primeiro símbolo na sequência de destino. Em seguida, a sequência de consulta é deslocada para a direita até que o primeiro símbolo na sequência de consulta é alinhado com o último símbolo da sequência alvo., Após cada turno, a parte sobreposta da consulta e as sequências alvo são comparadas para identificar novos MEMs. Três dos MEMs (Mx, My e Mz) são realçados com cores diferentes a serem usadas para a explicação posterior
no modelo de pontuação affine-gap, a pontuação de alinhamento é calculada usando Eq., 1 onde Nm é o número de jogos que cada um recebendo uma pontuação de Rm,Nx é o número de desfasamentos de cada um recebendo uma incompatibilidade pena de Px,N é o número de aberturas aberturas de cada um recebendo uma lacuna aberta pena de Po e Ng é o comprimento total de todos os espaços, cada lacuna receber uma lacuna extensão pena de Pg. Haveria uma abertura para cada grupo de abertura contínua. Por exemplo, se há duas aberturas no alinhamento, onde o comprimento da primeira abertura é de três e o comprimento da segunda abertura é de quatro, então há duas aberturas de abertura (No=2) e o comprimento total da abertura é de sete (Ng=3+4=7).,
Dada a lista de todos os MEMs, o alinhamento pode ser calculado usando parcial alinhamentos. Por exemplo, considere MEMs MX, My e Mz em Fig. 3b.os alinhamentos parciais feitos tomando diferentes combinações de Mx, My e Mz, juntamente com o número de partidas, desfasamentos e lacunas, bem como as pontuações de alinhamento resultantes são mostrados na Fig. 4. O alinhamento que só inclui Mx e Mz resulta na maior pontuação de alinhamento., Note que, My e Mz se sobrepõem e quando ambos são considerados no mesmo alinhamento a sobreposição é excluída da Mz. Considerando todos os MEMs na Fig. 3b resulta em muitas mais combinações onde nenhum deles atinge uma pontuação mais elevada.
Todas as combinações possíveis de MEMs no alinhamento
Examinando todas as combinações possíveis de MEMs seria exaustiva., Na seção” algoritmo de alinhamento ” descrevemos um algoritmo de programação dinâmica Novo DP-MEM que eficientemente Encontra a melhor combinação sem considerar todos os casos. DP-MEM precisa saber quais partes das sequências correspondem, mas não os símbolos reais nas sequências. A entrada para DP-MEM é o posicionamento de MEMs no alvo e nas sequências de consulta que são obtidas durante o processo de extração MEM descrito na seção “extração MEM”., Como os MEMs são representados com suas posições e como o número de correspondências, desfasamentos e lacunas são computados quando os MEMs são combinados em um alinhamento são explicados no restante desta seção. A figura 5 é outro exemplo de alinhamento com seis MEMs (M1 a M6) que formam o alinhamento entre a sequência de destino T e a sequência de consulta Q. para simplificar, não há sobreposição entre MEMs neste exemplo. Cada MEM Mi é representado como um tripleto de números inteiros: as posições iniciais em T E Em Q (STi e SQi respectivamente) e seu comprimento (Li)., As posições finais em T e em Q podem ser computadas mais tarde (Φ2E do algoritmo 2). A tabela 1 indica o comprimento e a posição de M1 a M6 em T e em Q.
Um exemplo de alinhamento com destaque MEM
No caso de haver ambos desfasamentos e lacunas entre Mi e Mj, todas as lacunas são consideradas contínuas para reduzir a diferença de penalidade aberta (apenas uma diferença de penalidade aberta é aplicada para uma diferença contínua). Assim, para todos os MEMs adjacentes que têm lacunas entre eles, apenas é aplicada uma penalidade aberta., A colocação de desfasamentos e a única lacuna contínua não é importante, pois não afetaria a pontuação de alinhamento. Assumimos que a pena de desajustamento é constante (isto é normal para sequências de ADN).
mem extraction
There are methods to extract maximal exact matches between lengthy sequences such as an entire genome. No entanto, estes métodos baseiam-se no pré-processamento e indexação de uma ou ambas as sequências, o que é uma operação demorada. Por exemplo, em DNA read aligner, o genoma de referência é indexado uma vez, e o mesmo índice é usado cada vez que uma nova leitura é alinhada., Estamos à procura de um algoritmo rápido para identificar MEMs entre sequências relativamente curtas que mudam para cada alinhamento. Um método de Força bruta para este problema (arquivo adicional 1: Seção II) é lento e ineficiente(com a complexidade de O (n3)). Propomos um método paralelo rápido de nível bit para acelerar o processo de extração MEM. Nosso método de extração MEM é baseado na mudança e comparar as operações mostradas na Fig. 3b. o primeiro passo é representar sequências com vetores de bits, onde A, C, T e G são codificados como 00, 01, 10 e 11, respectivamente (ficheiro adicional 1: Secção III)., A figura 6 ilustra um par de sequências de exemplo, juntamente com as representações bit-vector correspondentes. Em um computador commodity, a palavra máquina é geralmente 64 bits que podem acomodar 32 símbolos nucleotídeos. Uma vez que uma sequência é geralmente maior que 32 Símbolos, o bit-vector correspondente é armazenado em múltiplas palavras da máquina. Cada operação em vetores de bits de sequências de tamanho n de símbolos actua em \(\laceil \frac {n}{32} \rceil \) palavras da máquina.
a Representação de sequências de bits-vetores. Saída do XOR (X) com MEMs realçados. Bordas de bits do vetor (E) identifica o início e o fim de cada MEMs
Com bit-vetores de representação de sequências, deslocando uma seqüência de um símbolo é o mesmo que mudar o bit-vetor de dois bits, e a comparação de seqüências pode ser feito com a instrução XOR (32 símbolos de cada vez). Na saída XOR (X), 00 significa que os símbolos são correspondidos, e uma sequência de 00s mostra um MEM., Um conjunto de operações de shift e bitwise como mostrado no algoritmo 1 calcula X e subsequentemente o bit-vector de aresta (E) no qual o início e o fim de cada MEM são realçados com bits de set (bits com um valor de um). A figura 6 mostra os vetores de bits X e E com MEMs realçados. O posicionamento dos MEMs em sequências é então calculado a partir do bit-vector da aresta (ficheiro adicional 1: Secção IV).,
algoritmo de Alinhamento
Em “Abordagem” a seção, nós mostrar-se que, considerando diferentes combinações de MEMs e de computação o alinhamento pontuação correspondente ao alinhamento, pode-se identificar a combinação de MEMs que resulta no máximo alinhamento de pontuação. No entanto, examinar toda a combinação possível de MEMs é uma solução ingênua. Uma maneira mais sistemática de encontrar o alinhamento eficientemente é usar programação dinâmica.
Programação Dinâmica é o método de abordar a solução para um problema, definindo e resolvendo problemas menores., Soluções para subproblemas são usadas para resolver um problema maior a cada passo. O processo é repetido até que todos os subproblemas sejam resolvidos. Eventualmente, a solução para um dos subproblemas seria a solução para o problema inicial. Quando todos os subproblemas são resolvidos um processo de backtracking identifica uma série de soluções que contribuem para a solução final. Na programação dinâmica, deve haver uma ordenação dos dados de entrada ao longo dos quais o procedimento de recursão prossegue.
ordenamos todos os MEMs de acordo com a posição da sua sequência de consulta Final (EQ)., Os MEMs que terminam na mesma posição são ordenados de forma arbitrária. O subproblema J é encontrar o alinhamento das subseqüências de T E Q que terminam em JTH MEM Mj (T E Q respectivamente). Vamos mostrar que esta ordenação do MEM é suficiente para suportar a recursão correta.
na lista ordenada de MEMs, EQi=EQj indica que um dos Mi ou Mj sobrepõe-se completamente ao outro MEM na sequência da consulta. Uma vez que em Φ2B do algoritmo 2 a região de sobreposição é excluída, Mi e Mj não podem estar no mesmo alinhamento., Assim, os subproblemas ith e jth são resolvidos independentemente uns dos outros e a ordem de i E j na lista ordenada pode ser arbitrária. Se EQk>EQj (k>j na lista ordenada), Mk não poderia ser uma parte do alinhamento que termina em Mj. Assim, os subproblemas jth podem ser resolvidos independentemente da solução para o subproblema kth. Note que também é possível classificar MEMs com base na sua posição final na sequência-alvo (ET) usando uma justificação semelhante.
nosso algoritmo de programação dinâmica proposto (DP-MEM) é elaborado no algoritmo 2., Por exemplo, MEMs extraídos na Fig. 3b, a tabela de programação dinâmica e o valor intermédio calculados no algoritmo são apresentados nos figos. 7 e 8, respectivamente. A entrada para DP-MEM é a lista de MEMs onde cada MEM (Mj) é um tripleto de inteiros . A segunda entrada n é o número de MEMs na lista. A saída S é a pontuação de alinhamento para as sequências. O algoritmo imprime os índices de todos os MEMs que formam o alinhamento onde o primeiro e o último números impressos são os índices do mais à direita e do mais à esquerda no alinhamento, respectivamente., Todas as etapas do algoritmo 2 são comentadas do seguinte modo:
Dynamic programming table used in Algorithm 2 to process extracted MEMs in Fig. 3b. as células I E j representam o valor de \(S_{i}^j}\). As células vazias não são avaliadas em Φ2. A avaliação das células com marcação cruzada é ignorada em Φ2A. o valor inicial de Sj é calculado em Φ1. O valor Final de Sj e sua fonte (o que maximiza Sj) são realçados para cada linha. O SJ mais alto (S13) é a pontuação de alinhamento., O M13 é o último MEM no alinhamento e o MEM antes do MW = M3. Desde W=-1,M3 é o primeiro MEM no alinhamento. O sistema de pontuação para esse alinhamento é o Rm=2,Px=3,Po=4 e Pe=1
os valores Intermédios para calcular \(S_{i}^{j}\) na Fig. 7. Note que Sij nesta figura refere-se a \(s_{i}^{j}\)
-
Φ1: pontuação de cada MEM para todos os seus símbolos correspondentes., Note que existem símbolos de correspondência Lj no Mj. Sj representa a maior pontuação de alinhamento para o alinhamento final em Mj. Inicializar o Sj nesta etapa é semelhante à Computação da pontuação de alinhamento parcial quando apenas o Mj está incluído no alinhamento. W é usado para rastrear. O valor de -1 indica que o Sj atual é obtido considerando MJ sozinho no alinhamento.
-
Φ2: computando Sj para cada MEM (Mj)., Para calcular Sj, para cada MEM Mi onde Mi aparece antes de Mj na lista, o algoritmo adiciona Mj ao alinhamento que termina em Mi (estendendo alinhamentos encontrados anteriormente) e procura a extensão que maximiza Sj (resolvendo um subproblema maior usando subproblemas previamente resolvidos).
-
Φ2A: ignorar a extensão quando não é possível. If ETi>ETj then Mi contains part of target sequence which is beyond the alignment ending at Mj and the extension is not possible. Se EQi=EQJ ou ETi=ETj ou SQi≥SQj ou STi≥STj, então um dos mes sobrepõe-se totalmente ao outro MEM., Neste caso, Mi e Mj não podem estar em um alinhamento juntos.
-
Φ2B: computando o comprimento da sobreposição entre Mi e Mj. Se \({MO}_{i}^{j}\) for menor ou igual a zero, então não existe sobreposição.
-
Φ2D: Se existe sobreposição, excluindo-se a sobreposição do Mj
-
Φ2E: calcular a posição final do Mj em T e P.
-
Φ2F: Calcular a distância (número de símbolos) entre Mi e Mj em T e P.
-
Φ2G: Computação número de disparidades e as lacunas entre Mi e Mj.,
-
Φ2H: computando a penalidade para os desfasamentos e lacunas entre Mi e Mj (\(P_{i}^j}\)). Se existir uma diferença, apenas uma diferença de penalidade aberta é subtraída.
-
Φ2I: Computing alignment score \(\left (S_{i}^j}\right)\) when Mj is added to the alignment ending at Mi. A pontuação para todos os símbolos correspondentes em Mj (Lj×Rm) é adicionada à pontuação de alinhamento para o alinhamento que termina em Mi (Si). Em seguida, a penalidade pelas diferenças e discrepâncias entre o Mi e o Mj\(\esquerda (p_{i}^j}\direita)\) é subtraída.,
-
Φ2J: se a extensão do Mj ao alinhamento que termina no Mi resulta numa pontuação \(\esquerda (S_{i}^j}\direita)\) superior à pontuação actual para o Mj (Sj), então a nova pontuação é guardada no Sj. Também W está definido para I para manter o controle do Mi que maximiza a pontuação para Mj.
-
Φ2K: restaurar o valor de Mj antes da exclusão para que Mj possa ser usado em outras extensões de alinhamento.
-
Φ3: à procura do MEM com o Sj mais elevado. Este MEM é o último MEM no alinhamento (Me)., A maior pontuação (Se) é devolvida como S, que é a maior pontuação de alinhamento para as sequências dadas. O índice do MEM que maximiza o Sj é armazenado em e para começar a recuar de mim.
-
Φ4: no alinhamento, o MEM anterior imediato para mim é aquele que maximiza a pontuação de alinhamento para mim. O índice de tal Mem é armazenado em W. como resultado, a iteração de f←w visita o índice de todos os MEMs no alinhamento. Quando W é igual a -1, Mf é o primeiro MEM no alinhamento e a iteração é interrompida.,
Φ2C: conservar uma cópia de Mj antes de excluir sobreposições.
no nosso algoritmo, não penalizamos discrepâncias e lacunas antes do primeiro MEM e depois do último MEM no alinhamento. Isto resulta em um algoritmo de alinhamento local. Considerando estas penalidades, o algoritmo gera um alinhamento global (arquivo adicional 1: Seção V).
A equação para calcular \(P_{i}^{j}\) em Φ2H do Algoritmo 2 assume que não há nenhum símbolo correspondente entre T e Q na área entre Mi e Mj (todos os símbolos são contados como as inadequações ou falhas)., Embora esta suposição não seja verdadeira para todos os IA, é sempre verdade para o ia que leva ao máximo \(S_{i}^j}\) que supera o efeito da suposição ser incorreta para outros ia. Como prova, suponha que há um símbolo correspondente na área entre Mi e Mj. O símbolo correspondente seria um MEM (Mk). Mk já está estendido para o alinhamento que termina em Mi. Assim, ao estender Mj para Mk uma pontuação mais elevada é alcançada quando comparada com a extensão Mj para Mi.
Chaining colinear seeds as discussed in have been widely used in the alignment of large sequences, i.e. genome-to-genome alignment., Também tem sido usado para identificar regiões candidatas para uma leitura dado um conjunto de MEMs na BWA. Algoritmos de acorrentamento com pontuação são semelhantes ao algoritmo de programação dinâmica que propusemos (DP-MEM). No entanto, existem diferenças que tornam o DP-MEM adequado para alinhamento emparelhado de sequências curtas. DP-MEM leva em conta que todos os MEMs dentro de um determinado tamanho de gap são fornecidos na entrada e otimiza o número de iteração no algoritmo. A DP-MEM também implementa uma abordagem heurística para compensar o efeito das MEMs curtas removidas da lista de entrada, resultando em lacunas entre MEMs.,
de Optimização
Dado seqüências de comprimento n, o algoritmo para extrair MEMs (fornecidas em “MEM de extração” secção) requer 2(n−1) shift e 2n−1 operações de comparação no bit-vetores (cada ato em \(\lceil \frac {n}{32} \rceil \) máquina de palavras) que resultam em um algoritmo com complexidade de O(n2) para produz borda bit-vetores para um dado par de seqüências. A complexidade da função que calcula o posicionamento dos MEMs a partir do bit-vector de aresta e os ordena com base no EQ ainda está por ser adicionada. Além disso, se MEMs são extraídos, Φ2 do algoritmo 2 (DP-MEM) tem a complexidade de O(m2)., Considerando a complexidade da extração do MEM e DP-MEM, O MEM-Align é muito mais lento do que os algoritmos de alinhamento disponíveis. Para acelerar o processo, apresentamos várias otimizações para MEM-Align que alcança um tempo de execução mais rápido, sacrificando a precisão. Por outro lado, introduzimos métodos para melhorar a precisão com uma perda mínima de desempenho.alinhamento de bandas
alinhamento de bandas
alinhamento de bandas é um método heurístico conhecido para acelerar o processo de alinhamento. Esta técnica limita o padrão das lacunas no alinhamento (ficheiro adicional 1: Secção VI)., Consequentemente, se o alinhamento entre duas sequências não seguir este padrão, o algoritmo não identificará o alinhamento. Na programação dinâmica tradicional, o alinhamento é obtido após calcular o valor de todas as células da tabela. No entanto, com a otimização do alinhamento de bandas, apenas células no diâmetro e próximo da diagonal são avaliadas. gl é a largura da banda em alinhamento em que as células mais distantes do que gl ao diâmetro não são avaliadas. Células mais escuras na Fig. 1 mostrar o caso em que gl=1.,ao contrário da abordagem tradicional de programação dinâmica, MEM-Align não tem uma tabela similar para aplicar alinhamento de bandas. No entanto, descobrimos que podemos simular o mesmo efeito limitando o número de operações de deslocamento no processo de extração MEM. Por exemplo, se mudarmos a sequência de consulta para gl para a direita e para a esquerda, alcançaremos alinhamento com a faixa de gl. Alinhamento de bandas reduz a complexidade da extração do MEM de O(n2) para O(n.(2gl+1)), onde o gl é um valor pequeno e fixo. Assim, a complexidade da extração MEM é O(n) quando o alinhamento de bandas é aplicado., Além disso, com o referido alinhamento de bandas, é provável que menos MEMs sejam extraídos, o que acelera os passos algorítmicos subsequentes.
remoção de MEM curta duração
observamos que a maioria dos mem extraídos são curtos e são o resultado de símbolos de correspondência aleatória. Para acelerar o MEM-Align, MEMs menores que sl são filtrados durante o processo de extração MEM. Isto reduz o número de MEMs a serem extraídos e processados (subsequentemente acelerando o algoritmo). Filtrar MEM curto é feito estendendo o algoritmo 1 com um conjunto de operações shift e bitwise (arquivo adicional 1: Seção VII).,
Por outro lado, há casos raros em que MEMs curtos fazem parte do alinhamento; por exemplo, um símbolo de correspondência rodeado por desfasamentos. Sem ter todos os MEMs na lista de entrada, o DP-MEM não é capaz de encontrar o mesmo alinhamento que encontra quando todos os MEMs existem na lista de entrada. A fim de compensar os MEMs curtos perdidos na entrada, modificamos Φ2H de DP-MEM para considerar a possibilidade de ter curtas correspondências entre MEMs (arquivo adicional 1: Seção VIII).
pode haver casos mais difíceis em que, no alinhamento, existem múltiplas MEMs curtas entre duas MEMs (ver Fig. 9)., A única maneira de identificar corretamente a pontuação para a área entre Mi e Mj em Φ2H é aplicar um alinhamento global para esta região. No entanto, Φ2H é uma operação frequente e deve permanecer rápido. Consequentemente, decidimos superar parcialmente o problema limitando possíveis casos (um método heurístico).
Um exemplo que mostra várias curto MEM na pequena área entre a Mi e Mj em um alinhamento
Se existem lacunas na área entre Mi e Mj, nós assumimos que há apenas uma contínua lacuna para a extremidade esquerda ou para a extremidade direita da área. Então, apenas dois alinhamentos são possíveis para a área., O número de símbolos correspondentes é contado para ambos os casos de forma sequencial e o que resulta em correspondências máximas é considerado como o número de correspondências entre o ia e o Mj (ficheiro adicional 1: Secção IX). A comparação sequencial é uma operação cara e nós concebemos um método para evitar a comparação sequencial quando possível (arquivo adicional 1: Seção X).
qualquer outro caso que não se encaixe na suposição acima resulta em um alinhamento com uma pontuação mais baixa., No entanto, tendo em conta a baixa taxa de lacunas e desajustamentos, a possibilidade de existirem múltiplas lacunas e desajustamentos numa pequena área é baixa.
extensão de alinhamento eficiente
em Φ2 de DP−MEM, Mj estende todos os alinhamentos que terminam em {M1…MJ-1} (se possível). No entanto, para cada Mj existe um subconjunto menor Ωj {{M1 … Mj-1} tal que ao estender Mj a todos os alinhamentos que terminam em um Mi ω Ωj o alinhamento que termina em Mj é encontrado (Eq. 2). Por outras palavras, haveria menos \(S_{i}^j}\) a ser avaliado. Definição do conjunto Ωj e a prova de Eq. 2 são fornecidos no ficheiro adicional 1: Secção XI., A definição de Ωj é afetada quando a otimização de remoção de MEM curta é aplicada (arquivo adicional 1: Secção XII).
Híbrido de alinhamento
Para manter a precisão do algoritmo, decidimos utilizar um método híbrido, que é uma combinação de MEM-Alinhar e Smith-Waterman algoritmo. Definimos três casos em que o alinhamento MEM pode ser impreciso., Se o alinhamento de um par de sequências cair em um desses casos, usamos o algoritmo Smith-Waterman para alinhar sequências. Estes casos são:
-
Quando as sequências são repetitivas, e o número de MEMs extraídos excede o limiar TM. Descobrimos que MEM-Align pode produzir alinhamento impreciso ao alinhar sequências repetitivas. Um valor TM adequado diminui a possibilidade de comunicação de alinhamento impreciso com um aumento negligenciável do tempo médio de processamento.,
-
Quando a pontuação de alinhamento calculada para o alinhamento gerado pelo MEM-Align é inferior a uma TS-limiar. Este caso ocorre principalmente quando há uma lacuna no alinhamento que não pode ser identificado devido ao alinhamento de bandas.
-
Quando não há mais tempo do que sl para ser extraído (um caso raro)., Se sl for definido como um valor elevado e a semelhança entre sequências for baixa,
embora o envio de pares de sequências para um algoritmo externo resulte em cálculos adicionais, o número de sequências enviadas para o algoritmo externo permanece pequeno se forem escolhidos valores adequados para TM e TS.
saltando MEMs distantes
quando a distância entre Mi e Mj é grande, não é provável que Mi e Mj como MEMs adjacentes no alinhamento., Portanto, o algoritmo salta a extensão se a distância entre Mi e Mj for maior que um limiar TD (reduzindo ainda mais o número de \(s_{i}^j}\) a ser avaliado). Esta optimização melhora ligeiramente o desempenho, com um efeito secundário negligenciável na precisão.
