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,
.PNG)
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.
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.
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
- ↑ 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