Artigos

13.3: Visualizando Similaridade e Distância


Na seção anterior, vimos como o grau de semelhança ou distância entre os padrões de vínculos de dois atores com outros atores pode ser medido e indexado. Feito isso, o que acontecerá?

Muitas vezes é útil examinar as semelhanças ou distâncias para tentar localizar agrupamentos de atores (ou seja, maiores do que um par) que são semelhantes. Ao estudar os padrões maiores de quais grupos de atores são semelhantes a outros, também podemos obter algum insight sobre "e quanto" as posições do ator são mais críticas para torná-las mais semelhantes ou mais distantes.

Duas ferramentas comumente usadas para visualizar padrões de relacionamento entre variáveis ​​também são muito úteis na exploração de dados de redes sociais. Quando criamos uma matriz de semelhança ou distância descrevendo todos os pares de atores, podemos estudar a semelhança das diferenças entre as relações de "casos" da mesma forma que estudaríamos as semelhanças entre os atributos.

Nas próximas duas seções, mostraremos exemplos muito breves de como o escalonamento multidimensional e a análise de cluster hierárquica podem ser usados ​​para identificar padrões em matrizes de similaridade / distância ator a ator. Ambas as ferramentas são amplamente utilizadas em análises fora de rede; existem grandes e excelentes literaturas sobre as muitas complexidades importantes do uso desses métodos. Nosso objetivo aqui é fornecer apenas uma introdução muito básica.

Ferramentas de agrupamento

O agrupamento hierárquico aglomerativo de nós com base na similaridade de seus perfis de laços com outros casos fornece uma "árvore de junção" ou "dendograma" que visualiza o grau de similaridade entre os casos - e pode ser usado para encontrar classes de equivalência aproximadas.

Ferramentas> Cluster> Hierárquico prossegue colocando inicialmente cada caso em seu próprio cluster. Os dois casos mais semelhantes (aqueles com o índice de similaridade medido mais alto) são então combinados em uma classe. A semelhança desta nova classe com todas as outras é então calculada com base em um dos três métodos. Com base na matriz de similaridade recém-calculada, o processo de junção / recálculo é repetido até que todos os casos sejam "aglomerados" em um único cluster. A parte "hierárquica" do nome do método se refere ao fato de que, uma vez que um caso tenha sido unido a um cluster, ele nunca é reclassificado. Isso resulta em clusters de tamanho crescente que sempre encerram clusters menores.

O método "Média" calcula a similaridade das pontuações médias no cluster recém-formado com todos os outros clusters; o método "Single-Link" (também conhecido como "vizinho mais próximo") calcula as semelhanças com base na semelhança do membro do novo cluster que é mais semelhante a cada caso que não está no cluster. O método "Complete-Link" (também conhecido como "vizinho mais distante") calcula semelhanças entre o membro do novo cluster que é menos semelhante a cada caso que não está no cluster. O método padrão é usar a média do cluster; os métodos de link único tendem a fornecer diagramas de junção longos e complexos; os métodos de vínculo completo tendem a fornecer diagramas de união altamente separados.

A distância de Hamming no envio de informações na rede Knoke foi calculada conforme mostrado na seção acima, e os resultados foram armazenados como um arquivo. Este arquivo foi então enviado para Ferramentas> Cluster> Hierárquico. Especificamos que o método "médio" deveria ser usado e que os dados eram "dissimilaridades". Os resultados são mostrados na Figura 13.9.

Figura 13.9: Agrupamento de distâncias de Hamming de envio de informações na rede Knoke

O primeiro gráfico mostra que os nós 1 e 9 eram os mais semelhantes e unidos primeiro. O gráfico, a propósito, pode ser renderizado como um dendograma mais polido usando Ferramentas> Dendograma> Desenhar nos dados salvos da ferramenta de cluster. Na próxima etapa, existem três clusters (casos 2 e 5, 4 e 7 e 1 e 9). A junção continua até (na etapa 8 (^ text {th} )) todos os casos são aglomerados em um único cluster. Isso dá uma imagem clara da semelhança dos casos e dos agrupamentos ou classes de casos. Mas há realmente oito imagens aqui (uma para cada etapa da união). Qual é a solução "certa"?

Novamente, não há uma resposta única. A teoria e um conhecimento substantivo dos processos que deram origem aos dados são o melhor guia. O segundo painel "Medidas de adequação do cluster" pode ser de alguma ajuda. Existem vários índices aqui, e a maioria (normalmente) fornecerá respostas semelhantes. À medida que avançamos da direita (etapas mais altas ou quantidades de aglomeração) para a esquerda (mais grupos, menos aglomeração), o ajuste melhora. O índice E-I costuma ser mais útil, pois mede a proporção entre o número de laços dentro dos clusters e os laços entre os clusters. Geralmente, o objetivo é obter classes que sejam altamente semelhantes internamente e bastante distintas externamente. Aqui, alguém pode ser mais tentado pela solução da etapa 5 (^ text {th} ) do processo (clusters de 2 + 5, 4 + 7, 1 + 9, e os outros sendo clusters de item único )

Para serem significativos, os clusters também devem conter uma porcentagem razoável dos casos. O último painel mostra informações sobre os tamanhos relativos dos clusters em cada estágio. Com apenas 10 casos agrupados em nosso exemplo, isso não é terrivelmente esclarecedor aqui.

O UCINET fornece duas ferramentas adicionais de análise de cluster que não discutiremos em detalhes aqui - mas que você pode querer explorar. Ferramentas> Cluster> Otimização permite que o usuário selecione, a priori, uma série de classes e, em seguida, usa o método de análise de cluster escolhido para ajustar os casos às classes de maneira ideal. Isso é muito semelhante à técnica de otimização estrutural que discutiremos a seguir. Ferramentas> Cluster> Adequação de Cluster pega uma classificação fornecida pelo usuário (uma partição ou arquivo de atributo), ajusta os dados a ela e relata a qualidade do ajuste.

Ferramentas de escala multidimensional

Normalmente, nosso objetivo na análise de equivalência é identificar e visualizar "classes" ou clusters de casos. Ao usar a análise de cluster, estamos assumindo implicitamente que a semelhança ou distância entre os casos reflete como uma dimensão subjacente única. É possível, entretanto, que haja múltiplos "aspectos" ou "dimensões" subjacentes às semelhanças observadas de casos. A análise de fator ou componente pode ser aplicada a correlações ou covariâncias entre os casos. Alternativamente, o escalonamento multidimensional pode ser usado (não métrico para dados que são inerentemente nominais ou ordinais; métrico para valores).

O MDS representa os padrões de similaridade ou dissimilaridade nos perfis de empate entre os atores (quando aplicado a adjacências ou distâncias) como um "mapa" no espaço multidimensional. Este mapa nos permite ver o quão "próximos" os atores estão, se eles se "agrupam" no espaço multidimensional e quanta variação existe ao longo de cada dimensão.

As Figuras 13.10 e 13.11 mostram os resultados da aplicação Ferramentas> MDS> MDS não métrico à matriz de adjacência bruta da rede de informações de Knoke e selecionando uma solução bidimensional.

Figura 13.10: Coordenadas bidimensionais de MDS não métricas de adjacência de informações de Knoke

"Stress" é uma medida de inadequação do ajuste. Ao usar o MDS, é uma boa ideia olhar para uma variedade de soluções com mais dimensões, para que você possa avaliar até que ponto as distâncias são unidimensionais. As coordenadas mostram a localização de cada caso (1 a 10) em cada uma das dimensões. O caso um, por exemplo, está no quadrante esquerdo inferior, tendo pontuações negativas tanto na dimensão 1 quanto na dimensão 2.

O "significado" das dimensões às vezes pode ser avaliado comparando casos que estão nos pólos extremos de cada dimensão. As organizações de um pólo são "públicas" e as do outro "privadas"? Ao analisar dados de redes sociais, não é incomum que a primeira dimensão seja simplesmente a quantidade de conexão ou o grau dos nós.

Figura 13.11: Mapa bidimensional de MDS não métrico de adjacência de informações de Knoke

A Figura 13.11 representa graficamente os nós de acordo com suas coordenadas. Neste mapa, estamos procurando por agrupamentos restritos significativos de pontos para identificar casos que são altamente semelhantes em ambas as dimensões. Em nosso exemplo, há muito pouca similaridade (exceto, talvez, os nós 1 e 2).

As ferramentas de clustering e dimensionamento podem ser úteis em muitos tipos de análise de rede. Qualquer medida das relações entre os nós pode ser visualizada usando esses métodos - adjacência, força, correlação e distância são mais comumente examinadas.

Essas ferramentas também são bastante úteis para examinar a equivalência. A maioria dos métodos de avaliação de equivalência gera medidas de proximidade ou similaridade de ator por ator nos perfis de empate (usando regras diferentes, dependendo do tipo de equivalência que estamos tentando medir). O Cluster e o MDS costumam ser bastante úteis para entender os resultados.


Comparando dados multivariados

Use métodos simétricos quando você não tiver uma hipótese sobre a direção dos efeitos entre duas matrizes.

Compare matrizes de similaridade / distância

“Esses métodos não devem ser usados ​​para testar hipóteses sobre as relações entre as tabelas de dados originais.”

Teste de Mantel

  • Caixa 10.2 na pág. 600
  • Testa se as distâncias entre os objetos estão monotonicamente relacionadas entre si.
  • Passos:
    • Calcule uma estatística de Mantel que é o produto escalar dos valores (não diagonais) na (metade) das duas matrizes de distância. (Veja a Figura 10.19 na pág. 599)
      • (z_M ): distâncias brutas
      • (r_M ): use distâncias padronizadas e divida por (n (n-1) / 2 - 1 ) para obter o valor entre -1 e 1.

      Análise de Similaridade (ANOSIM) e PERMANOVA

      • ANOSIM testa se as distâncias entre os grupos são maiores do que dentro dos grupos.
      • PERMANOVA testa se a distância difere entre os grupos. Isso não estava na leitura original para a aula, mas você pode encontrar o método em Anderson (2001).
      • Ambos os testes são sensíveis a projetos desequilibrados e diferenças na dispersão (variância) dentro dos grupos (por exemplo, não é bom quando seus grupos têm variabilidade diferente). Anderson e Walsh (2013) conduziram uma comparação baseada em simulação de PERMANOVA e ANOSIM e descobriram que PERMANOVA é mais robusto em geral para dados ecológicos, mas ainda sensível à heterogeneidade de variância entre os grupos. Você deve avaliar essa suposição antes de usar qualquer um dos testes.
      • Etapas ANOSIM:
        • Classifique as distâncias dentro da matriz de distância e, em seguida, calcule a estatística (R = frac<>) - classificação ruim_)>) .
        • Teste se (R ) é maior do que o esperado permutando objetos originais.
        • Calcule uma relação F comparando (F sim frac<>>), onde (SS ) significa somar a soma dos quadrados das distâncias.
        • Teste se (F ) é menor do que o esperado ao acaso, permutando os objetos originais.

        Compare duas tabelas de dados

        • Métodos frequentemente usados ​​para analisar em conjunto a variação de duas comunidades no mesmo conjunto de sites.
        • Não use para comparar matrizes que medem as mesmas variáveis ​​(por exemplo, estudos antes-depois ou experimentos de controle de impacto) porque a análise não sabe que as variáveis ​​são as mesmas. (Em vez disso, use RDA ou PCA.)
        • Ambas as análises de co-inércia e procrustes podem lidar com mais variáveis ​​do que observações (por exemplo, mais espécies do que locais), bem como colinearidade entre as variáveis.
        • A análise de correlação canônica (CCorA) geralmente não é recomendada porque assume normalidade multivariada de variáveis ​​quantitativas.

        Análise de co-inércia

        • Cria uma ordenação baseada em duas covariâncias entre duas matrizes de dados e plota ambas as matrizes no mesmo espaço de ordenação junto com suas variáveis.
        • Passos:
          • Calcule a matriz de covariância cruzada entre as variáveis ​​em duas matrizes.
          • Calcule os valores próprios e os vectores próprios da matriz de covariância. Os vetores próprios fornecem os eixos da ordenação.
          • Projete as duas matrizes no espaço de ordenação e use as setas para conectar os dois pontos medidos no mesmo objeto.
          • Adicione setas para cada uma das variáveis ​​nas duas matrizes.
          • Nesse caso, faça uma análise de coordenadas principais nas duas martices de distância e use os eixos correspondentes aos autovalores positivos como a entrada das tabelas de dados na análise de co-inércia.

          Análise Procrustes

          • Cria uma ordenação de “compromisso” de duas matrizes medidas nos mesmos objetos para visualizar as diferenças entre duas martices.
          • O algoritmo gira as matrizes para minimizar a soma das distâncias quadradas entre os objetos correspondentes.
          • Muito semelhante à análise de co-inércia, mas usa matrizes diferentes para plotagem.
          • Método PROTEST: calcula a estatística simétrica ortogonal de Procrustes (m ^ 2 ) para medir a similaridade entre duas matrizes de dados.

          Análise de múltiplos fatores

          • Usado para comparar conjuntos de variáveis ​​- todas as variáveis ​​dentro de um conjunto devem ser do mesmo tipo.
          • Calcule o PCA em cada conjunto de variáveis ​​separadamente e, em seguida, calcule o PCA de eixos de PC concatenados de todos os conjuntos (que são primeiro multiplicados por um número para dar peso igual a cada conjunto).
          • A variável do projeto é definida no gráfico de ordenação para comparar sua correlação.

          Pacotes e funções R

          vegan: funções para análise de composição da comunidade

          • manto ()
          • protesto()
          • anosim ()
          • adonis () para PERMANOVA
          • betadisper () para testar a homogeneidade de variâncias dentro do grupo

          ecodista: funções para análise de dissimilaridade ecológica

          macaco: funções para análise filogenética

          ade4: funções para análise multivariada para ecologistas

          • mantel.rtest ()
          • coinertia () em duas ordenações separadas produzidas por dudi.pca () ou dudi.pco ()
          • mfa () em um dataframe ktab que divide as variáveis ​​em “blocos” produzidos por ktab.data.frame ()

          Exemplo de Análise

          Comparações de matrizes

          Os testes a seguir são usados ​​para testar relacionamentos entre matrizes de associação (ou seja, matrizes de distância ou similaridade) e não dados brutos! + Teste de Mantel + Teste de Mantel parcial + Regressão múltipla em matrizes de distância

          Teste de Mantel

          Compare duas matrizes de distância / similaridade que foram obtidas independentemente uma da outra


          Normalizado, métrico, similaridade e distância

          Embora o tópico possa parecer simples, existem muitos algoritmos diferentes para medir a semelhança ou distância do texto. Portanto, a biblioteca define algumas interfaces para categorizá-las.

          Similaridade e distância (normalizadas)

          • StringSimilarity: Os algoritmos de implementação definem uma semelhança entre as strings (0 significa que as strings são completamente diferentes).
          • NormalizedStringSimilarity: Os algoritmos de implementação definem uma similaridade entre 0,0 e 1,0, como Jaro-Winkler por exemplo.
          • StringDistance: Os algoritmos de implementação definem uma distância entre as strings (0 significa que as strings são idênticas), como Levenshtein, por exemplo. O valor da distância máxima depende do algoritmo.
          • NormalizedStringDistance: esta interface estende StringDistance. Para a implementação de classes, o valor da distância calculada está entre 0,0 e 1,0. NormalizedLevenshtein é um exemplo de NormalizedStringDistance.

          Geralmente, os algoritmos que implementam NormalizedStringSimilarity também implementam NormalizedStringDistance e similarity = 1 - distance. Mas existem algumas exceções, como semelhança e distância de N-Gram (Kondrak).

          Distâncias métricas

          A interface MetricStringDistance: Algumas das distâncias são, na verdade, distâncias métricas, o que significa que verificam a desigualdade do triângulo d (x, y) & lt = d (x, z) + d (z, y). Por exemplo, Levenshtein é uma distância métrica, mas NormalizedLevenshtein não é.

          Muitos algoritmos de busca do vizinho mais próximo e estruturas de indexação dependem da desigualdade triangular.


          Métodos

          InteGO2 é um aplicativo da web baseado em arquitetura de navegador / servidor (BS). O back-end é implementado usando Python 2.7 e a estrutura de desenvolvimento web web.py. MySQL é usado para gerenciamento de dados. No front-end, JavaScript e XML assíncrono (AJAX) e JavaScript Object Notation (JSON) são usados ​​para transmissão de dados eficiente entre o navegador e o servidor. Canvas HTML5 e cytoscape.js [15] são usados ​​como o motor gráfico para a visualização. As anotações GO de todos os organismos são baixadas do site GO (http://www.geneontology.org/) e são atualizadas automaticamente para garantir que as anotações mais recentes sejam usadas. InteGO2 incorporar uma API de mapeamento de gene ID fornecida pelo site da UniProt (http://www.uniprot.org/). Um usuário pode enviar uma lista de genes para uma ferramenta da web usando um dos 98 tipos diferentes de IDs de genes.


          Resultados e discussão

          PhenoSimWeb contém principalmente duas operações a serem executadas: 1) digitar um conjunto de fenótipos e especificar os parâmetros correspondentes, 2) visualizar e baixar as semelhanças do fenótipo. Além disso, os usuários podem enviar uma lista de fenótipos para prever os genes ou doenças associadas a um determinado conjunto de fenótipos.

          Entradas do usuário

          A interface do usuário de PhenoSimWeb pode ser dividido em três partes: entrada de fenótipos (Fig. 1a), seleção de medição de similaridade (Fig. 1b) e entrada de informações do usuário (Fig. 1c).

          A página principal de entrada do PhenoSimWeb. Todo o processo pode ser dividido em três partes, incluindo: uma) inserir fenótipo, gene ou conjunto de dados de doenças, b) escolhendo medição de similaridade de fenótipo, c) digitar informações experimentais do usuário opcionalmente

          PhenoSimWeb contém principalmente três módulos funcionais: (1) dada uma lista de fenótipos, calcular as semelhanças de pares entre os fenótipos de entrada (2) dada uma lista de genes ou doenças, calcular as semelhanças de pares agregando as semelhanças de fenótipos associados a determinados genes ou doenças (3) dada uma lista de fenótipos, identificar os genes ou doenças mais associados aos fenótipos dados com base em sua similaridade baseada em HPO. A interface de entrada para cada módulo funcional é apresentada a seguir.

          Interface de entrada para cálculo de similaridade de fenótipo

          PhenoSimWeb fornece três métodos para o usuário inserir uma lista de fenótipos. O usuário pode inserir texto que descreve fenótipos, selecionar fenótipos de bancos de dados existentes e inserir um conjunto de fenótipos diretamente (ver Fig. 1a). Permitir a entrada de texto é importante, uma vez que os fenótipos dos pacientes são sempre descritos no texto, como registros clínicos. PhenoSimWeb usa a ferramenta de anotação Annotator [39] do National Center for Biomedical Ontology (NCBO) para converter o texto de entrada em termos HPO correspondentes. Para os outros dois métodos de entrada, apenas HPO ID e Nome são permitidos na versão atual.

          Interface de entrada para cálculo de similaridade de genes (ou doenças)

          PhenoSimWeb fornece dois métodos para o usuário inserir uma lista de genes (ou doenças). O usuário pode selecionar genes ou doenças de bancos de dados existentes e inserir um conjunto de genes ou doenças diretamente (ver Fig. 2). Atualmente, PhenoSimWeb só pode calcular semelhanças para genes ou doenças anotadas por termos HPO, uma vez que suas semelhanças são baseadas nas semelhanças fenotípicas baseadas em HPO.

          A página de entrada da Web para calcular a semelhança de genes. Esta parte fornece dois tipos de entrada, incluindo o conjunto de genes de entrada diretamente e seleção de genes do banco de dados

          Interface de entrada para gene associado a fenótipo ou previsão de doença

          Nesta parte (Fig. 3), os usuários podem inserir o conjunto de fenótipos na caixa de texto à esquerda e selecionar o tipo de alvo a ser previsto, como gene ou doença. Os usuários também podem fornecer uma lista de genes ou doenças alvo na caixa de texto correta para verificar se esses genes ou doenças estão associados ao conjunto de fenótipos de entrada. Se o usuário não fornecer um gene específico ou conjunto de doenças, PhenoSimWeb compararia o conjunto de fenótipos com todos os genes ou doenças envolvidas no HPO.

          A página da Web de entrada de previsão de genes ou doenças semelhantes. Os usuários inserem fenótipo definido na caixa de texto à esquerda, gene ou doença definido na caixa de texto direita e selecionam o tipo de previsão

          Após a etapa de entrada de dados, os usuários podem selecionar uma medida de similaridade semântica para o cálculo de similaridade de fenótipo. Uma nova medida proposta chamada PhenoSim e outras quatro medidas de similaridade amplamente utilizadas estão disponíveis para escolha. As descrições detalhadas dessas medições estão na subseção a seguir.

          Na última etapa, os usuários podem inserir o endereço de e-mail e o nome do usuário experimental opcionalmente. E se os usuários fizerem isso, o aplicativo enviará uma notificação para a caixa de correio especificada quando todo o trabalho for concluído. E o aplicativo irá validá-lo para verificação de erros se todas as informações de entrada forem enviadas. O processo de validação verifica principalmente o formato dos fenótipos de entrada, listas de fenótipos, textos de fenótipos, genes, listas de genes, doenças, listas de doenças e todos os parâmetros especificados pelo usuário. E se houver algum erro na entrada, os usuários serão notificados imediatamente. Após o processo de validação, o aplicativo irá calcular a similaridade por meio de medidas especificadas, que os usuários escolheram na etapa dois, entre fenótipos, genes ou doenças, e visualizar a rede associada ao fenótipo.

          Todos os trabalhos enviados são executados por um programador de trabalhos no servidor back-end de PhenoSimWeb. Assim que todos os trabalhos forem concluídos, um email de notificação será enviado para a caixa de correio especificada, se os usuários digitarem o endereço de email na etapa três. Além disso, a web irá para a página da web do resultado experimental, se o usuário abrir a página de envio e mantê-la ativada.

          A página da web de resultados experimentais exibe os resultados detalhados do cálculo de similaridade e os valores p correspondentes (Fig. 4). As outras informações detalhadas no processo de cálculo, como o método de cálculo, também são exibidas na página de resultados. Além disso, os usuários podem baixar o resultado experimental e as informações correspondentes pelos links da página.

          Os resultados do cálculo da lista de fenótipos. E PhenoSim calculou o valor P correspondente, além da similaridade semântica

          Interface de visualização

          PhenoSimWeb fornece uma página da web visual intuitiva e funcional para exibir os resultados de similaridade. A interface de visualização de PhenoSimWeb (ver Fig. 5) exibe a rede de associação de fenótipo resultante e a rede de associação de gene ou doença com base nas semelhanças de fenótipo correspondentes na página da web de visualização, em que um nó representa um termo, como fenótipo ou gene ou doença, e uma borda entre qualquer dois termos interconectados indicam que a pontuação de similaridade de borda é maior do que o limite de similaridade de borda, que os usuários inserem na Fig. 5a. Os usuários podem implementar a navegação interativa da interface visual usando o mouse de forma conveniente (Fig. 5c). Além disso, os usuários também podem ativar o painel de operação do nó clicando com o botão direito do mouse em um nó (consulte o painel na Fig. 5e). Usando o painel de operação de nó, os usuários podem executar várias operações de nó, como: inserir o termo atual na lista selecionada no painel A, exibir informações do termo no painel superior direito D, inserir o termo na lista bloqueada, excluir o termo atual da lista bloqueada e definir cor de fundo do nó atual em verde.

          A interface de visualização de PhenoSimWeb para explorar fenótipo, gene ou semelhanças funcionais de doença com base em HPO. Painel c mostra o termo rede de associação e, entre a rede de associação, um nó indica um termo (fenótipo, gene ou doença) e uma borda entre quaisquer dois termos interconectados indica que a pontuação de similaridade de borda é maior do que o limite de similaridade de borda, que os usuários inserem no painel uma. Painel b mostra a distribuição geral de pontuações de similaridade para todos os pares de termos de entrada, os usuários podem regular o limite de similaridade de borda no painel uma por esta distribuição intuitivamente. Os vizinhos dos termos escolhidos recentemente são mostrados no painel d. Os usuários podem adicionar, informar, bloquear, desbloquear e sinalizar um termo no painel de operação do nó e. Além disso, painel f mostrar a sub-rede selecionada pelo usuário

          Os usuários podem arrastar a barra de limite ou digitar um valor específico diretamente para ajustar o limite de similaridade de borda, e a rede mudará simultaneamente (ver Fig. 5a). PhenoSimWeb também fornece vários layouts de gráfico diferentes para visualização de gráfico (consulte a Tabela 1). A Figura 5b mostra a distribuição geral de pontuações de similaridade para todos os pares de termos de entrada, os usuários podem regular o limite de similaridade de borda no painel A por esta distribuição intuitivamente. O termo resultante rede de associação é pesquisado no painel de exibição de rede (ver Fig. 5c). Além disso, os usuários podem especificar um grupo de termos no painel A ou painel de operação do nó para selecionar sub-redes (ver Fig. 5f). E o painel de informações do termo (Fig. 5d) exibe os vizinhos do termo selecionado atualmente. Ao clicar em um ID ou nome de termo no painel de informações, os usuários podem obter informações mais abrangentes sobre este termo no site (http://compbio.charite.de).

          Um exemplo ilustrativo do uso de PhenoSimWeb

          Nesta seção, pegamos a lista de amostra de fenótipos no site como entrada para demonstrar como usar PhenoSimWeb este aplicativo da web para calcular a semelhança de pares para um conjunto de fenótipos. Selecionamos o “PhenoSim” como a medida de similaridade HPO na Fig. 1b. E os parâmetros na Fig. 1c são opcionais, o usuário pode digitar um endereço de e-mail e deixar o nome de usuário correspondente ou não. No final, clicamos no botão “enviar” para enviar o trabalho.

          Assim que todos os programas de back-end forem finalizados, os resultados dos cálculos serão exibidos no site (Fig. 4). Os usuários também podem baixar os resultados dos cálculos clicando no botão “Clique aqui para baixar o arquivo de resultados desta corrida”. Além disso, os usuários podem clicar no botão “Exibir” para ver a visualização gráfica dos resultados experimentais correspondentes (ver Fig. 5). Ajustando o limiar de similaridade de fenótipo para fenótipo no painel A, poderíamos obter duas redes de associação de fenótipo contrastantes (ver Fig. 6). Além disso, também podemos exibir a rede de associação com diferentes layouts, que são interpretados na Tabela 1, ou seja, cola e grade, selecionando os layouts de gráfico no painel A (ver Fig. 7).

          O diagrama de comparação de duas redes de associação de fenótipo contrastantes com diferentes limiares de similaridade de fenótipo para fenótipo. O limite da borda da esquerda é 0 e da direita é 0,1

          O diagrama de comparação da visualização da rede de associação de fenótipo com dois layouts de gráfico diferentes. O tipo de cola e a grade são usados ​​na figura esquerda e direita, respectivamente

          Além das funções acima, também podemos escolher vários fenótipos (ou seja, HP: 0000080, HP: 0000069, HP: 0030037 e HP: 0000025) como os fenótipos interessados ​​e anexá-los à caixa em branco no painel A usando o painel de operação do nó . Em seguida, a sub-rede correspondente, que contém os fenótipos selecionados, é destacada (a figura da direita na Fig. 8). Além disso, os usuários também podem adicionar todos os vizinhos dos fenótipos interessados ​​na rede destacada clicando em “Alternar exibição de vizinho” no painel A (a figura à esquerda na Fig. 8). Além disso, os usuários podem ver o detalhe de cada fenótipo clicando em nós entre a rede no painel C, e as informações detalhadas do fenótipo escolhido serão mostradas na Fig. 5d.

          O diagrama de comparação da construção de sub-redes selecionando fenótipos interessados. O da direita exibe que quatro fenótipos interessados ​​(HP: 0000080, HP: 0000069, HP: 0030037 e HP: 0000025) são escolhidos. O esquerdo exibe todos os nós escolhidos e seus vizinhos diretamente conectados

          Medidas de similaridade implementadas

          PhenoSimWeb fornece cinco medidas de similaridade semântica baseadas em HPO para todos os usuários. Apresentaremos brevemente essas cinco medidas na parte seguinte.

          1) PhenoSim

          Resumidamente, PhenoSim é um método baseado em conteúdo de informação restrito por caminho para medição de similaridade semântica de fenótipo e inclui um componente de redução de ruído para modelar os dados de fenótipo de paciente com ruído [36]. Todo o processo de PhenoSim contém três etapas: Primeiro, ele constrói uma rede fenotípica N usando ontologias de fenótipo e associações gene-fenótipo. Em segundo lugar, dado um conjunto de fenótipos clínicos de um paciente, ele filtra ruídos com base em N usando o PageRank. Finalmente, ele calcula as semelhanças de fenótipo com um novo método baseado em conteúdo de informação restrito por caminho.

          Comparado com outras abordagens existentes, PhenoSim melhora efetivamente o desempenho da medição de similaridade do fenótipo e aumenta a precisão do gene causador baseado no fenótipo e da previsão de doenças.

          2) Baseado em conteúdo de informação (Resnik)

          Resnik et al. [40] propôs um método para calcular a similaridade semântica baseada em ontologia entre quaisquer duas ontologias fenotípicas, integrando o conteúdo de informação (IC) com a estrutura da ontologia. O conteúdo da informação de qualquer termo representa a especificidade do termo. Os termos em um nível inferior de Ontologia tendem a ter IC e vise verso mais altos. Além disso, o IC de dois termos fenotípicos é o ancestral comum mais baixo desses dois termos na estrutura da ontologia. Dado o termo da ontologia t, e o conteúdo de informação correspondente de t poderia ser definido como IC(t)=−registro(|Dt|/|D|), onde Dt e D são conjuntos de doenças anotadas para t e o termo raiz. Matematicamente, dados quaisquer dois termos de ontologia tuma e tb, deixar tMICA representa o seu ancestral comum mais informativo (MICA), a semelhança semântica de tuma e tb é calculado da seguinte forma:

          onde d_<>> ) e D representam o conjunto de anotações de tMICA e o conjunto de todas as anotações envolvidas na Ontologia, respectivamente.

          3) Conteúdo de informação aprimorado com base (Lin)

          Lin et al. [41] considerou o Conteúdo da Informação (IC) de dois termos tuma e tb além do IC de seu ancestral comum mais informativo, comparando com a medida de Resnik. E a equação de cálculo da similaridade do termo ontologia é definida como:

          4) Com base em conteúdo de informação normalizado (Schlicker)

          Schlicker et al. [35] normalizou a medida baseada em conteúdo de informação (Resnik) e utilizou uma função de ponderação para regular a pontuação geral:

          5) Medida Jiang-Conrath (JC)

          Comparando a medida de Resnik, Jiang-Conrath [34] considerou o conteúdo de informação do termo tuma e tb e a distância entre o ancestral comum mais público além do conteúdo de informação de tuma e tb. E Jiang-Conrath calcula similaridade semântica como:


          Cálculo da matriz de distância

          Preparação de dados

          Usaremos os dados USArests como conjuntos de dados de demonstração. Usaremos apenas um subconjunto dos dados, pegando 15 linhas aleatórias entre as 50 linhas do conjunto de dados. Isso é feito usando a função amostra() Em seguida, padronizamos os dados usando a função escala():

          Funções e pacotes R

          Existem muitas funções R para calcular distâncias entre pares de observações:

          1. dist() Função de base R [Estatísticas pacote]: Aceita apenas dados numéricos como entrada.
          2. get_dist() função [fato extra pacote]: Aceita apenas dados numéricos como entrada. Em comparação com a função dist () padrão, ela suporta medidas de distância baseadas em correlação, incluindo os métodos “pearson”, “kendall” e “spearman”.
          3. margarida() função [agrupar pacote]: Capaz de lidar com outros tipos de variáveis ​​(por exemplo, nominal, ordinal, (a) binário simétrico). Nesse caso, o coeficiente de Gower será usado automaticamente como a métrica. É uma das medidas mais populares de proximidade para tipos de dados mistos. Para obter mais detalhes, leia a documentação R do margarida() função (?margarida).

          Todas essas funções calculam distâncias entre linhas de dados.

          Calculando a distância euclidiana

          Para calcular a distância euclidiana, você pode usar a base R dist() função, como segue:

          Observe que os valores permitidos para o método de opção incluem um dos seguintes: “euclidiano”, “máximo”, “manhattan”, “canberra”, “binário”, “minkowski”.

          Para tornar mais fácil ver as informações de distância geradas pelo dist() função, você pode reformatar o vetor de distância em uma matriz usando a as.matrix() função.

          Nesta matriz, o valor representa a distância entre os objetos. Os valores na diagonal da matriz representam a distância entre os objetos e eles próprios (que são zero).

          Nesse conjunto de dados, as colunas são variáveis. Portanto, se quisermos calcular distâncias de pares entre variáveis, devemos começar transpondo os dados para ter variáveis ​​nas linhas do conjunto de dados antes de usar o dist() função. A função t() é usado para transpor os dados.

          Calculando distâncias baseadas em correlação

          Correlation-based distances are commonly used in gene expression data analysis.

          A função get_dist()[factoextra package] can be used to compute correlation-based distances. Correlation method can be either pearson, spearman ou kendall.

          Computing distances for mixed data

          A função daisy() [cluster package] provides a solution (Gower’s metric) for computing the distance matrix, in the situation where the data contain no-numeric columns.

          The R code below applies the daisy() function on Flor data which contains factor, ordenou e numeric variables:


          Restriction Fragment Length Polymorphism (RFLP) Analysis

          Restriction enzyme recognition sites are short (only a few nucleotides long), sequence-specific palindromes, and may be found throughout the genome. Thus, differences in DNA sequences in the genomes of individuals will lead to differences in distribution of restriction-enzyme recognition sites that can be visualized as distinct banding patterns on a gel after agarose gel electrophoresis. Restriction fragment length polymorphism (RFLP) analysis compares DNA banding patterns of different DNA samples after restriction digestion (Figure 13.15).

          RFLP analysis has many practical applications in both medicine and forensic science . For example, epidemiologists use RFLP analysis to track and identify the source of specific microorganisms implicated in outbreaks of food poisoning or certain infectious diseases. RFLP analysis can also be used on human DNA to determine inheritance patterns of chromosomes with variant genes, including those associated with heritable diseases or to establish paternity .

          Forensic scientists use RFLP analysis as a form of DNA fingerprinting , which is useful for analyzing DNA obtained from crime scenes, suspects, and victims. DNA samples are collected, the numbers of copies of the sample DNA molecules are increased using PCR , and then subjected to restriction enzyme digestion and agarose gel electrophoresis to generate specific banding patterns. By comparing the banding patterns of samples collected from the crime scene against those collected from suspects or victims, investigators can definitively determine whether DNA evidence collected at the scene was left behind by suspects or victims.

          Figure 13.15. RFLP analysis can be used to differentiate DNA sequences. In this example, a normal chromosome is digested into two fragments, whereas digestion of a mutated chromosome produces only one fragment. The small red arrows pointing to the two different chromosome segments show the locations of the restriction enzyme recognition sites. After digestion and agarose gel electrophoresis, the banding patterns reflect the change by showing the loss of two shorter bands and the gain of a longer band. [Credit: modification of work by National Center for Biotechnology Information]


          Dot Product

          One drawback of Euclidean distance is the lack of orientation considered in the calculation — it is based solely on magnitude. And this is where we can use our other two metrics. The first of those is the dot product.

          The dot product considers direction (orientation) and also scales with vector magnitude.

          We care about orientation because similar meaning (as we will often find) can be represented by the direction of the vector — not necessarily the magnitude of it.

          For example, we may find that our vector's magnitude correlates with the frequency of a word that it represents in our dataset. Now, the word Oi means the same as Olá, and this may not be represented if our training data contained the word Oi 1000 times and Olá just twice.

          So, vectors' orientation is often seen as being just as important (if not more so) as distance.

          The dot product is calculated using:

          The dot product considers the angle between vectors, where the angle is

          0, the cosθ component of the formula equals

          1. If the angle is nearer to 90 (orthogonal/perpendicular), the cosθ component equals

          0, and at 180 the cosθ component equals

          Portanto, o cosθ component increases the result where there is less of an angle between the two vectors. So, a higher dot-product correlates with higher orientation.

          Again, let’s apply this formula to our two vectors, uma e b:

          Clearly, the dot product calculation is straightforward (the simplest of the three) — and this gives us benefits in terms of computation time.

          However, there is one drawback. It is not normalized — meaning larger vectors will tend to score higher dot products, despite being less similar.

          For example, if we calculate a·a — we would expect a higher score than a·c (uma is an exact match to uma) But that’s not how it works, unfortunately.

          So, in reality, the dot-product is used to identify the general orientation of two vectors — because:

          • Two vectors that point in a similar direction return a positivo dot-product.
          • Two perpendicular vectors return a dot-product of zero.
          • Vectors that point in opposing directions return a negativo dot-product.

          R: clustering with a similarity or dissimilarity matrix? And visualizing the results

          I have a similarity matrix that I created using atormentar&mdasha tool for string similarity, and I wanted to plot some dendrograms out of it to see if I could find some clusters / groups in the data. I'm using the following similarity measures:

          • Normalized compression distance (NCD)
          • Damerau-Levenshtein distance
          • Jaro-Winkler distance
          • Levenshtein distance
          • Optimal string alignment distance (OSA)

          ("For comparison Harry loads a set of strings from input, computes the specified similarity measure and writes a matrix of similarity values to output")

          At first, it was like my first time using R, I didn't pay to much attention on the documentation of hclust , so I used it with a similarity matrix. I know I should have used a dissimilarity matrix, and I know, since my similarity matrix is normalized [0,1], that I could just do dissimilarity = 1 - similarity and then use hclust .

          But, the groups that I get using hclust with a similarity matrix are much better than the ones I get using hclust and it's correspondent dissimilarity matrix.

          I tried to use the proxy package as well and the same problem, the groups that I get aren't what I expected, happens.

          To get the dendrograms using the similarity function I do:

          With the dissimilarity matrix I tried:

          From (1) I get what I believe to be a very good dendrogram, and so I can get very good groups out of it. From (2) and (3) I get the same dendrogram and the groups that I can get out of it aren't as good as the ones I get from (1)

          I'm saying that the groups are bad/good because at the moment I have a somewhat little volume of data to analyse, and so I can check them very easily.

          Does this that I'm getting makes any sense? There is something that justify this? Some suggestion on how to cluster with a similarity matrizx. Is there a better way to visualize a similarity matrix than a dendrogram?


          13.3: Visualizing Similarity and Distance

          A library implementing different string similarity and distance measures. A dozen of algorithms (including Levenshtein edit distance and sibblings, Jaro-Winkler, Longest Common Subsequence, cosine similarity etc.) are currently implemented. Check the summary table below for the complete list.

          The main characteristics of each implemented algorithm are presented below. The "cost" column gives an estimation of the computational cost to compute the similarity between two strings of length m and n respectively.

          Normalized? Metric? Modelo Custo Typical usage
          Levenshtein distância Não sim O(m*n) 1
          Normalized Levenshtein distância
          similarity
          sim Não O(m*n) 1
          Weighted Levenshtein distância Não Não O(m*n) 1 OCR
          Damerau-Levenshtein 3 distância Não sim O(m*n) 1
          Optimal String Alignment 3 distância Não Não O(m*n) 1
          Jaro-Winkler similarity
          distância
          sim Não O(m*n) typo correction
          Longest Common Subsequence distância Não Não O(m*n) 1,2 diff utility, GIT reconciliation
          Metric Longest Common Subsequence distância sim sim O(m*n) 1,2
          N-Gram distância sim Não O(m*n)
          Q-Gram distância Não Não Perfil O(m+n)
          Cosine similarity similarity
          distância
          sim Não Perfil O(m+n)
          Jaccard index similarity
          distância
          sim sim Definir O(m+n)
          Sorensen-Dice coefficient similarity
          distância
          sim Não Definir O(m+n)
          Overlap coefficient similarity
          distância
          sim Não Definir O(m+n)

          [1] In this library, Levenshtein edit distance, LCS distance and their sibblings are computed using the dynamic programming method, which has a cost O(m.n). For Levenshtein distance, the algorithm is sometimes called Wagner-Fischer algorithm ("The string-to-string correction problem", 1974). The original algorithm uses a matrix of size m x n to store the Levenshtein distance between string prefixes.

          If the alphabet is finite, it is possible to use the method of four russians (Arlazarov et al. "On economic construction of the transitive closure of a directed graph", 1970) to speedup computation. This was published by Masek in 1980 ("A Faster Algorithm Computing String Edit Distances"). This method splits the matrix in blocks of size t x t. Each possible block is precomputed to produce a lookup table. This lookup table can then be used to compute the string similarity (or distance) in O(nm/t). Usually, t is choosen as log(m) if m > n. The resulting computation cost is thus O(mn/log(m)). This method has not been implemented (yet).

          [2] In "Length of Maximal Common Subsequences", K.S. Larsen proposed an algorithm that computes the length of LCS in time O(log(m).log(n)). But the algorithm has a memory requirement O(m.n²) and was thus not implemented here.

          [3] There are two variants of Damerau-Levenshtein string distance: Damerau-Levenshtein with adjacent transpositions (also sometimes called unrestricted Damerau–Levenshtein distance) and Optimal String Alignment (also sometimes called restricted edit distance). For Optimal String Alignment, no substring can be edited more than once.

          Normalized, metric, similarity and distance

          Although the topic might seem simple, a lot of different algorithms exist to measure text similarity or distance. Therefore the library defines some interfaces to categorize them.

          (Normalized) similarity and distance

          • StringSimilarity : Implementing algorithms define a similarity between strings (0 means strings are completely different).
          • NormalizedStringSimilarity : Implementing algorithms define a similarity between 0.0 and 1.0, like Jaro-Winkler for example.
          • StringDistance : Implementing algorithms define a distance between strings (0 means strings are identical), like Levenshtein for example. The maximum distance value depends on the algorithm.
          • NormalizedStringDistance : This interface extends StringDistance. For implementing classes, the computed distance value is between 0.0 and 1.0. NormalizedLevenshtein is an example of NormalizedStringDistance.

          Generally, algorithms that implement NormalizedStringSimilarity also implement NormalizedStringDistance, and similarity = 1 - distance. But there are a few exceptions, like N-Gram similarity and distance (Kondrak).

          The MetricStringDistance interface : A few of the distances are actually metric distances, which means that verify the triangle inequality d(x, y) <= d(x,z) + d(z,y). For example, Levenshtein is a metric distance, but NormalizedLevenshtein is not.

          A lot of nearest-neighbor search algorithms and indexing structures rely on the triangle inequality.

          Shingles (n-gram) based similarity and distance

          A few algorithms work by converting strings into sets of n-grams (sequences of n characters, also sometimes called k-shingles). The similarity or distance between the strings is then the similarity or distance between the sets.

          Some of them, like jaccard, consider strings as sets of shingles, and don't consider the number of occurences of each shingle. Others, like cosine similarity, work using what is sometimes called the profile of the strings, which takes into account the number of occurences of each shingle.

          For these algorithms, another use case is possible when dealing with large datasets:

          1. compute the set or profile representation of all the strings
          2. compute the similarity between sets or profiles

          The Levenshtein distance between two words is the minimum number of single-character edits (insertions, deletions or substitutions) required to change one word into the other.

          It is a metric string distance. This implementation uses dynamic programming (Wagner–Fischer algorithm), with only 2 rows of data. The space requirement is thus O(m) and the algorithm runs in O(m.n).

          This distance is computed as levenshtein distance divided by the length of the longest string. The resulting value is always in the interval [0.0 1.0] but it is not a metric anymore!

          The similarity is computed as 1 - normalized distance.

          An implementation of Levenshtein that allows to define different weights for different character substitutions.

          This algorithm is usually used for optical character recognition (OCR) applications. For OCR, the cost of substituting P and R is lower then the cost of substituting P and M for example because because from and OCR point of view P is similar to R.

          It can also be used for keyboard typing auto-correction. Here the cost of substituting E and R is lower for example because these are located next to each other on an AZERTY or QWERTY keyboard. Hence the probability that the user mistyped the characters is higher.

          Similar to Levenshtein, Damerau-Levenshtein distance with transposition (also sometimes calls unrestricted Damerau-Levenshtein distance) is the minimum number of operations needed to transform one string into the other, where an operation is defined as an insertion, deletion, or substitution of a single character, or a transposition of two adjacent characters.

          It does respect triangle inequality, and is thus a metric distance.

          This is not to be confused with the optimal string alignment distance, which is an extension where no substring can be edited more than once.

          The Optimal String Alignment variant of Damerau–Levenshtein (sometimes called the restricted edit distance) computes the number of edit operations needed to make the strings equal under the condition that no substring is edited more than once, whereas the true Damerau–Levenshtein presents no such restriction. The difference from the algorithm for Levenshtein distance is the addition of one recurrence for the transposition operations.

          Note that for the optimal string alignment distance, the triangle inequality does not hold and so it is not a true metric.

          Jaro-Winkler is a string edit distance that was developed in the area of record linkage (duplicate detection) (Winkler, 1990). The Jaro–Winkler distance metric is designed and best suited for short strings such as person names, and to detect typos.

          Jaro-Winkler computes the similarity between 2 strings, and the returned value lies in the interval [0.0, 1.0]. It is (roughly) a variation of Damerau-Levenshtein, where the substitution of 2 close characters is considered less important then the substitution of 2 characters that a far from each other.

          The distance is computed as 1 - Jaro-Winkler similarity.

          Longest Common Subsequence

          The longest common subsequence (LCS) problem consists in finding the longest subsequence common to two (or more) sequences. It differs from problems of finding common substrings: unlike substrings, subsequences are not required to occupy consecutive positions within the original sequences.

          It is used by the diff utility, by Git for reconciling multiple changes, etc.

          The LCS distance between strings X (of length n) and Y (of length m) is n + m - 2 |LCS(X, Y)| min = 0 max = n + m

          LCS distance is equivalent to Levenshtein distance when only insertion and deletion is allowed (no substitution), or when the cost of the substitution is the double of the cost of an insertion or deletion.

          This class implements the dynamic programming approach, which has a space requirement O(m.n), and computation cost O(m.n).

          In "Length of Maximal Common Subsequences", K.S. Larsen proposed an algorithm that computes the length of LCS in time O(log(m).log(n)). But the algorithm has a memory requirement O(m.n²) and was thus not implemented here.

          Metric Longest Common Subsequence

          Distance metric based on Longest Common Subsequence, from the notes "An LCS-based string metric" by Daniel Bakkelund. http://heim.ifi.uio.no/

          The distance is computed as 1 - |LCS(s1, s2)| / max(|s1|, |s2|)

          Normalized N-Gram distance as defined by Kondrak, "N-Gram Similarity and Distance", String Processing and Information Retrieval, Lecture Notes in Computer Science Volume 3772, 2005, pp 115-126.

          The algorithm uses affixing with special character ' ' to increase the weight of first characters. The normalization is achieved by dividing the total similarity score the original length of the longest word.

          In the paper, Kondrak also defines a similarity measure, which is not implemented (yet).

          Shingle (n-gram) based algorithms

          A few algorithms work by converting strings into sets of n-grams (sequences of n characters, also sometimes called k-shingles). The similarity or distance between the strings is then the similarity or distance between the sets.

          The cost for computing these similarities and distances is mainly domnitated by k-shingling (converting the strings into sequences of k characters). Therefore there are typically two use cases for these algorithms:

          Directly compute the distance between strings:

          Or, for large datasets, pre-compute the profile of all strings. The similarity can then be computed between profiles:

          Pay attention, this only works if the same KShingling object is used to parse all input strings !

          Q-gram distance, as defined by Ukkonen in "Approximate string-matching with q-grams and maximal matches" http://www.sciencedirect.com/science/article/pii/0304397592901434

          The distance between two strings is defined as the L1 norm of the difference of their profiles (the number of occurences of each n-gram): SUM( |V1_i - V2_i| ). Q-gram distance is a lower bound on Levenshtein distance, but can be computed in O(m + n), where Levenshtein requires O(m.n)

          The similarity between the two strings is the cosine of the angle between these two vectors representation, and is computed as V1 . V2 / (|V1| * |V2|)

          Distance is computed as 1 - cosine similarity.

          Like Q-Gram distance, the input strings are first converted into sets of n-grams (sequences of n characters, also called k-shingles), but this time the cardinality of each n-gram is not taken into account. Each input string is simply a set of n-grams. The Jaccard index is then computed as |V1 inter V2| / |V1 union V2|.

          Distance is computed as 1 - similarity. Jaccard index is a metric distance.

          Similar to Jaccard index, but this time the similarity is computed as 2 * |V1 inter V2| / (|V1| + |V2|).

          Distance is computed as 1 - similarity.

          Overlap coefficient (i.e., Szymkiewicz-Simpson)

          Very similar to Jaccard and Sorensen-Dice measures, but this time the similarity is computed as |V1 inter V2| / Min(|V1|,|V2|). Tends to yield higher similarity scores compared to the other overlapping coefficients. Always returns the highest similarity score (1) if one given string is the subset of the other.

          Distance is computed as 1 - similarity.

          SIFT4 is a general purpose string distance algorithm inspired by JaroWinkler and Longest Common Subsequence. It was developed to produce a distance measure that matches as close as possible to the human perception of string distance. Hence it takes into account elements like character substitution, character distance, longest common subsequence etc. It was developed using experimental testing, and without theoretical background.

          Use java-string-similarity in your project and want it to be mentioned here? Don't hesitate to drop me a line!