Mostrar código-fonte de Barrier

O aplicativo utiliza a triangulação dos pontos amostrais para identificar e testar barreiras geográficas de uma determinada variável. O seu uso é mais frequente em estudos de genética de populações, embora possa ser aplicado para qualquer variável em que medidas de diferenciação possam ser aferidas (e.g. variações morfométricas, diferenças entre sobrenomes).  As barreiras são identificadas em áreas onde uma determinada variável analisada mostra uma taxa abrupta de mudança. Para isto, o método utiliza-se a aplicação de uma abordagem geométrica em que são identificadas as localizações e as orientações das barreiras, mostrando os padrões geográficos das variáveis. Como método de testar a não-aleatoriedade da barreira identificada, é aplicado o bootstrap, onde a matriz é reamostrada e confiabilidade é expressa graficamente.

=== Bases Teóricas ===
O método se caracteriza como uma distribuição espacial não-paramétrica baseado no algoritmo de máxima diferença de Monmonier [http://onlinelibrary.wiley.com/doi/10.1111/j.1538-4632.1973.tb01011.x/abstract (1973)].

O '''''algoritmo de Monmonier''''' é utilizado para identificar limites, isto é, as áreas em que as diferenças entre as unidades amostrais são maiores. Consiste em uma análise da paisagem em que as amostras (pontos amostrais) são unidas usando uma rede de Delaunay (método gráfico para definir pontos adjacentes). Em seguida, traça-se uma perpendicular entre as amostras adjacentes com maior índice de distância e seguem-se perpendicularmente, sempre associadas aos mais altos valores de distância, até que se chegue a uma borda ou forme um círculo em torno de uma ou mais localidades (Figura 2). Com a utilização deste algoritmo tem-se a definição de grupos em ambos os lados de uma barreira.

Se os limites são a base para a divisão regional, o primeiro requisito é um índice de significância de fronteira. Um critério óbvio é a diferença de valor nas duas áreas adjacentes dividido pelo limite. Quando a regionalização é baseada em uma única variável X, a diferença  entre partes adjacentes i e j pode ser expressa por:

<math>D_ij=|X_i-X_j |</math>

A utilização de valores absolutos reconhece que a relevância de um limite não é afetada pelo sinal da diferença. Em ambientes digitais, o tempo de computação pode ser ligeiramente reduzido, tendo o quadrado da diferença:

<math>D_{ij^2}= \sum_{k=1}^m(X_ik-X_jk)^2</math>

[[Ficheiro:Delaunay_circumcircles_centers.png|ligação=https://pt.wikiversity.org/wiki/Ficheiro:Delaunay_circumcircles_centers.png|miniaturadaimagem|Dado um conjunto de vértices é construída uma triangulação de Delaunay para esse conjunto de pontos.]]

==== '''Triangulação de Delaunay''' ====
A triangulação foi concebida por Boris Delaunay, em 1934. É o método mais rápido de triangulação para conectar um conjunto de pontos (localidades) em um plano (mapa) com um conjunto de triângulos. É também a maneira mais direta de se conectar (triangular) pontos adjacentes no mapa.

Uma [[w:Triangulação_de_Delaunay|triangulação de Delaunay]] (TD) para um conjunto P de vértices deve atender à condição de Delaunay, que é: TD(P) é uma triangulação de Delaunay, tal que nenhum vértice de P permanece dentro do circuncírculo de qualquer triângulo em TD(P). A triangulação de Delaunay maximiza o menor ângulo de todos os triângulos, evitando ângulos internos muito pequenos.

==== '''Diagrama de Voronoi''' ====
Os diagramas de Voronoi permitem a subdivisão das regiões em um conjunto de áreas de abrangência, a fim de estabelecer relações de proximidades. Uma célula Voronoi é um conjunto de todos os pontos no dado espaço o qual a distância para o dado sítio não é maior que sua distância para os outros objetos.

No caso base, temos um conjunto finito de pontos ''{p<sub>1</sub>,...,p<sub>n</sub>}'' no Plano Euclidiano. Neste caso cada sítio ''p<sub>k</sub>'' é meramente um ponto, e corresponde a uma célula Voronoi R<sub>k</sub> consistindo em todos os pontos que possuem distância para p<sub>k</sub> menor do que a distância para qualquer outro local. Cada célula é obtida a partir da interseção de semiespaços e, portanto, é um [[polígono]] [[convexo]]. Os segmentos do diagrama de Voronoi são todos os pontos do plano equidistantes aos dois sítios mais próximos. Os vértices (nós) de Voronoi são os pontos equidistantes de três ou mais sítios.

O ''grafo dual'' para um Diagrama de Voronoi (no caso de um [[espaço Euclideano]] com pontos em sítios) corresponde a [[Triangulação de Delaunay]] para o mesmo conjunto de pontos.

O [[par de pontos mais próximo]] corresponde a duas células adjacentes do Diagrama de Voronoi.

[[Ficheiro:Delaunay_Voronoi.svg|ligação=https://pt.wikiversity.org/wiki/Ficheiro:Delaunay_Voronoi.svg|miniaturadaimagem|Conectando-se os centros das circunferências da triangulação de Delaunay, produz-se o Digrama de Voronoi (em vermelho).]]

=== '''Aplicações''' ===
* Linguística, com dados antropológicos (ex. estruturação através de variações no sobrenome)
* Genética
* Morfologia
* Biomedicina (ex. identificação de áreas em que as taxas de doença mudam rapidamente ou de identificação de diferentes taxas de expressão dos genes)

==== '''Uso e Aplicação em Estudos Genéticos''' ====
O ''software'' Barrier é frequentemente utilizado em estudos de genética de populações e em filogeografia. As informações obtidas a partir do sequenciamento para qualquer marcador molecular podem servir como base para a estimativa do [[wikipedia:Fixation_index|Índice de Fixação]] (Fst) ou outros métodos que estimem a variação genética. O Fst é uma medida de variação genética entre as populações, onde é estimado a partir de valores da variação alélica (Ɵ ou π ). A informação gerada é uma fração da variação entre as populações e a variação dentro das populações ([http://onlinelibrary.wiley.com/doi/10.1111/j.0014-3820.2000.tb01231.x/abstract Edwards & Beerli, 2000]):

<math>Fst={\theta_b-\theta_w\over\theta_b}

    Fst={\pi_b-\pi_w\over\pi_b}</math>

A estimativa de diferença gênica obtida entre as amostras é plotada em uma matriz, associada a um ponto amostral (localidade) previamente à triangulação. A localização da barreira é traçada de acordo com o algoritmo de Monmonier, onde os vértices com maiores valores de distância são utilizados para determinar se o fluxo gênico é baixo ou não existente.

==== '''Bootstrap''' ====
Para avaliar a confiabilidade e não aleatoriedade das barreiras identificadas pelo programa é utilizado o método de ''bootstrap''. A técnica utiliza a reamostragem com reposição, que permite estimar a acurácia e intervalo de confiança do método. O ''bootstrap'' no software Barrier é calculado a partir da matriz de dados inserida e indicado graficamente pela espessura da barreira gerada que quanto maior, mais confiável é a barreira identificada.

=== '''Premissas e Limitações''' ===
* Idealmente as populações devem ser regularmente espaçadas, onde a área sob investigação se aproxima de um polígono convexo. Populações irregularmente espaçadas podem levar a resultados ambíguos, criando até mesmo barreiras fictícias;
* Grandes áreas sem amostragem devem ser evitadas sempre que possível.
* O método baseado em triangulação apresenta a vantagem de que a distribuição irregular de amostras não é mascarada por interpolação;
* Algumas configurações topológicas de pontos amostrados não são adequados para análises de barreiras (e.g.pontos amostrados em transectos/linhas);
* A triangulação Delaunay foi idealizada para pontos em um plano. Alguns problemas podem surgir quando as amostras se encontram sobre uma superfície curva, tal como a superfície da terra, uma vez que não é possível projetar a posição destas amostras em um plano sem algum tipo de erro. Uma limitação do software Barrier é de não aceitar localizações geográficas com projeções em coordenadas planas. A triangulação pode ser comprometida afetando dessa maneira a delimitação das barreiras;
* Na delimitação de barreiras com utilização do software, erros podem ocorrer se houver coordenadas idênticas, impedindo o cálculo da triangulação;
* Erros também podem ocorrer se forem utilizadas matrizes com medidas de distância idênticas, pois neste caso não pode ser feita a decisão de direcionamento entre direita ou esquerda;
* A aplicação das distâncias da variável avaliada em distâncias geográficas é desejável quando as amostras são recolhidas num espaço tridimensional, isto é, quando a altitude do local de amostragem é levada em consideração, além da latitude e longitude.
* O método não é aplicável caso não seja possível obter uma matriz de distância para a variável analisada (e.g. variável genética/morfométrica).
* Novas premissas podem ser adicionadas e devem ser avaliadas caso a caso, de acordo com a variável selecionada para a análise (e.g. uso de distância genética – Fst/ uso da matriz morfológica com distâncias, logaritmizadas ou não).

=== Software ===

==== Barrier ====
O software '''''Barrier''''' calcula barreiras em uma triangulação de Delaunay utilizando o algoritmo de Monmonier. Os dados de entrada (inputs) necessários são as coordenadas geográficas da localização das populações e uma matriz de distância genética/morfométrica.

Os principais procedimentos que o software realiza podem ser sintetizados nos seguintes passos:

1)     A localização das amostras são espacializadas no mapa de acordo com as coordenadas geográficas;

2)     A triangulação de Delaunay é usada para conectar as posições geográficas das amostras no mapa;

3)     As distâncias genéticas (ou morfométricas) são calculadas entre as amostras adjacentes;

4)     O algoritmo de máxima diferença de Monmonier é utilizado para a identificação de barreiras.

[http://ecoanthropologie.mnhn.fr/software/barrier.html Manual do Software Barrier]

==== Programa R ====
O Programa R apresenta um pacote ''Adegent'' o qual permite de maneira gratuita a análise de barreiras utilizando o mesmo algoritmo do Barrier, o Algoritmo de Monmonier. A utilização da análise pelo R permite maior flexibilidade além do uso de um maior número de variáveis.

[http://adegenet.r-forge.r-project.org/ Link para download:]

[http://adegenet.r-forge.r-project.org/files/tutorial-basics.pdf Tutorial:]

=== Referências ===
[http://onlinelibrary.wiley.com/doi/10.1111/j.0014-3820.2000.tb01231.x/abstract Edwards, S., & Beerli, P. (2000). Perspective: gene divergence, population divergence, and the variance in coalescence time in phylogeographic studies. ''Evolution'', ''54''(6), 1839-1854.]

[http://s3.amazonaws.com/academia.edu.documents/42463289/IMPLEMENTATION_OF_MONMONIERS_ALGORITHM_20160209-8420-18714b6.pdf?AWSAccessKeyId=AKIAJ56TQJRTWSMTNPEA&Expires=1478038827&Signature=Mgw542qssRomqTa1wQQrHjWVc0o%3D&response-content-disposition=inline%3B%20filename%3DImplementation_of_Monmoniers_algorithm_o.pdf Ivetić, V., Isajev, V., Stavretović, N., & Mladenović-drinić, S. (2010). Implementation of Monmonier’s algorithm of maximum differences for the regionalization of forest tree populations as a basis for the selection of seed sources. ''Archives of Biological Sciences'', ''62''(2), 425-430].

[http://www.sciencedirect.com/science/article/pii/S0169534703000089 Manel, S., Schwartz, M. K., Luikart, G., & Taberlet, P. (2003). Landscape genetics: combining landscape ecology and population genetics. ''Trends in ecology & evolution'', ''18''(4), 189-197.]

[https://muse.jhu.edu/article/170182/summary Manni, F., Guerard, E., & Heyer, E. (2004). Geographic patterns of (genetic, morphologic, linguistic) variation: how barriers can be detected by using Monmonier's algorithm. ''Human biology'', ''76''(2), 173-190.]

[http://onlinelibrary.wiley.com/doi/10.1111/j.1538-4632.1973.tb01011.x/abstract Monmonier, M. S. (1973). Maximum‐difference barriers: An alternative numerical regionalization method. ''Geographical analysis'', ''5''(3), 245-261.]

[[Categoria:Matemática]]