Matriz de distâncias

Na matemática, ciência da computação e na teoria dos grafos, uma matriz de distâncias é uma matriz (array bidimensional) contendo as distâncias, tomadas em pares, de um conjunto de pontos. Esta matriz terá um tamanho de N×N onde N é o número de pontos, nós ou vértices (muitas vezes em um grafo).

Comparação com matrizes relacionadas

Comparação com matrizes de adjacência

Matrizes de distância estão relacionadas com matrizes de adjacência, com as diferenças que (a)  que a última apenas fornece as informações de que vértices estão ligados mas não diz nada sobre os custos ou distâncias entre os vértices e (b)  uma entrada de uma matriz de distância é menor, se dois elementos estão mais próximos, ao passo que vértices "próximos" (conectados) produzem entradas maiores em uma matriz de adjacência.

Comparação com a matriz de distância euclidiana

Ao contrário de uma matriz de distância euclidiana, a matriz não precisa ser simétrica -- isto é, os valores xi,j não necessariamente são iguais aos valores xj,i. Da mesma forma, os valores da matriz não estão restritos a reais não-negativos (como seriam na matriz de distância euclidiana) mas podem ter valores negativos, zeros ou números imaginários dependendo da métrica de custo utilizada e do uso específico. Embora seja frequentemente o caso, matrizes de distância não se restringem a ser oca - ou seja, eles podem ter entradas não zeradas na diagonal principal.

Exemplos e usos

Exemplo 1: Distância em um grafo

Por exemplo, suponha devam ser analisadas as distâncias entre os átomos do 3-Etilhexano,

(3-Etilhexano)

A matriz de distâncias seria:

Átomo 1 2 3 4 5 6 7 8
1 0 1 2 3 4 5 3 4
2 1 0 1 2 3 4 2 3
3 2 1 0 1 2 3 1 2
4 3 2 1 0 1 2 2 3
5 4 3 2 1 0 1 3 4
6 5 4 3 2 1 0 4 5
7 3 2 1 2 3 4 0 1
8 4 3 2 3 4 5 1 0

Exemplo 2: Distância entre pixeis

Por exemplo, suponha que esses dados devam ser analisados, onde a distância euclidiana em pixeis seja a métrica de distância.

Dados brutos

A matriz de distâncias seria:

a b c d e f
a 0 184 222 177 216 231
b 184 0 45 123 128 200
c 222 45 0 129 121 203
d 177 123 129 0 46 83
e 216 128 121 46 0 83
f 231 200 203 83 83 0

Estes dados podem ser visualizados em forma gráfica como um mapa de calor. Nesta imagem, preto denota uma distância de 0 e branco é a distância máxima.

Visão gráfica

Em bioinformática, matrizes de distâncias são usadas para representar estruturas de proteínas de uma forma independente de coordenadas, bem como as distâncias entre duas seqüências de pares no espaço de seqüências.[1]

Eles são usados em alinhamentos estruturais e seqüenciais, e para a determinação de estruturas de proteínas a partir de RMN ou cristalografia de raios X.

Às vezes é mais conveniente expressar dados como em uma matriz de similaridade.

Ver também

Referências

  1. Nei, Masatoshi; Kumar, Sudhir (2000). «Phylogenetic Inference:Distance Methods». Molecular Evolution and Phylogenetics (em inglês). Oxford: Oxford University Press. p. 87-113. ISBN 0-19-513585-7