Manual of the user
Contents
1. Number of matrices Ignored data F Start import at line fi E Start import at column fi Lines between matrices i E djk 4 4 J 0O 00 00 00 00 00 02 OO 00 0O Oh OO OO Po 0 A Cr on Data preview setup Preview matrix n fi E Clll E Extract data Oo 7 0 DJ ee a od T Oo 0 54675 6 46556 Auto extract Cancel Matris size 225 2 26 Number of matrices 1 226 lines successfully extracted Figure 18 The Dialog box that opens when you are attempting to extract a distance matrix distance matrices co ordinates from a data file In the File preview window left you have a view of the file data to be ex tracted In the central window Data preview you see what kind of extraction will result according to the extraction parameters that are located on the right part of the window Extraction settings are divided in three frames The Matrix size value cannot be changed it just informs you about the expected size of the matrix according to the number of samples populations that constitute the map The Square ma trix option enables the preview of imported matrix as squared or triangular The Number of matrices box tells the program how many distance matrices are expected in the matrix data file With a single ma trix this option has to be set at 1 whereas you have to tell the program how many2. large to e saved By this window you can select an alternative drive destination Amout of available space 53 ME corel You can export computed maps as BMP Windows Bitmap or PS Postscript files Corre sponding options are available trough the File scroll down menu in the major menu bar Fig 39 PS exported maps can be edited by a PS editor but due to some problems we could not identify the resulting vectorial image may not exactly correspond to the image displayed by the software concerning the thickness and size of points and edges The advantage of BMP files is that they look exactly like the map displayed on the screen but they are of heavi est weight in terms of memory and can t be edited Triangulation Editor 6Points dwt j Figure 39 ERE Eo Layers Tools Points Zoom In the File scroll down menu New Ctrlt N properties Tor h r n Open Ctrl O h you have Export options con Close Ctrl F4 cerning the vectorial format Save Ctrl S Postscript or graphic format Save as Bit MEN PostScript ps Bitmap Printer setup Bitmap bmp Print Ctrl P Quit Ctri Q 2 5 5 1 Exporting a pixelized image Even though BMP images can be of lower quality and memory consuming if compared to PS images they represent a simple and fast method to export the results The BMP graphic format has been chosen since it is the standard format of the MS Windows platform and since
3. Fig 3B re BS aN IANN nee SSS of ee NSS _ ta al oH oe ESSA veaa Figure 2 A B A Voronoi tessellation in blue of the points Samples populations according to geographic locations of figure 1 in red B Voronoi tessellation in blue of the points Samples populations according to geographic locations of figure 1 in red and the corresponding Delaunay triangulation in green Voronoi diagrams as defined by the author imply that all possible points inside a polygon are closest to its centroid the location of the sampled population than to any other It means that we divide the geographic space S in m subspaces S satisfying the following properties Uje VIOL a vee DIST Xf Wj lt DIST Xf Wy Vitj x 8 with w centroid of S Furthermore each vertex of a Voronoi polygon is located at the intersection of three edges in other words such vertex will be equidistant from three samples populations repre senting the centroids of surrounding polygons As a consequence each vertex of the Voronoi tessellation will correspond to the intersection of the medians of the triangle Fig 3D In gt Voronoi M G 1908 Nouvelles application des param tres continus a la th orie des formes quadratiques deuxi me m moire recherche sur le parall loedres primitifs Journal Reine Angew Math 134 198 207 other words a Voronoi vertex it is the center of the circle circums
4. New option from the scroll down File window in the menu bar and then choose the file with the coordinates Fig 5 from a standard open file window not shown Soon after a dialog box enabling the import opens Import coordi nates data Fig 6 This box is divided in three parts i on the left a preview of the ASCII file ii in the middle a preview of the coordinates as they will be extracted according to cur rent parameters iii on the right the user settings consisting in the raw and column from which the import has to be started and of the number of extracted points You can select to work only on a sub sample of such points by stopping the import at a given line it is up to you to give a certain rank to the samples that ought to be ordered as in the corresponding distance matrix and vice versa in order to proceed to a partial meaningful import of a subset of samples Let s imagine you have 100 samples and 50 of them correspond to first sampling and the remaining 50 correspond to the second sampling If you order them consecutively be ing the 7 50 those of the 1 sampling and 57 100 those of the Xt sampling you can then compute the barriers in two times then visualizing the two samplings separately We remind here that the software automatically interprets as columns all numbers separated by tabs and spaces see section 6 Known bugs It is possible to define if coordi nates are in X Y order or in Y X order Each time one of these para
5. One barrier computed N times The bootstrap score S associated to each edge of N barriers is 1 lt Sedges lt N where N is the number of resampled matrices The sum of all the bootstrap scores Sedges can be highly variable as with phylogenetic trees and therefore there is no possible statistics that can lead to a consensus barrier Anyhow barriers flow trough the Voronoi tessellation and this phenomenon is often visible on the map since the sum of the number of barriers passing in a given section between two arbitrary points A and B is often equal to the total number of computed barriers that is to the number of matrices see example G in Fig 23 Differently from an approach currently used with bootstrap phylogenetic trees we do not suggest to represent only those edges of the tessellation that are supported by a score higher than a choused cut off value let s say Sedges gt Y2 N because in this case a pattern that may be visually obvious will disappear or be less visible example F in Fig 23 4 1 2 Two or more barriers computed N times If the interpretation of the bootstrap scores of the first Monmonier s barrier computed on N matrices is quite easy some difficulties may appear when computing more barriers because it will be almost impossible to distinguish the flow of the first N barriers from the flow of the second N barriers When computing barriers on a single overall matrix labels unambigu ously i
6. The ea ta first step is to click on the Barriers scroll down Ram veall I 1 aim E menu of the command bar and to select the New option Figure 16 Setting window enabling you to specify the pa rameters for barrier analysis With the first button Load matrix data you will jump to the data file selection Fig 17 and to the data import dialog window Fig 18 Once that the distance matrix Monmonier algorithm specifications o Driene datafile o CATEMP Hononga 7 3 2002 1 3 17d Jabs 1 maties loaded zee 226 t 226 Kumbar of bamers 1 a Ci BR Ce CP re ca has been successfully imported you can set the Bangor labels following parameters Number of barriers Option enabling you to T Show rept _ choose how many barriers you want to compute io CYe C Mo A You can directly set such number up to 10 barri Ere anrea ET Yes E ers and set a higher number of barriers by on Clicking the right button of your mouse rMonmonier tie In this box you can type a title for your project Barrier labels By this frame you can select the kind of labels you want to be displayed to identify bar riers on the map in a hierarchical order as 1 2 3 or as a b c or as I Ill Ill In the example of Fig 12 the a b c option was selected If you have single matrix data the No box will be automatically checked in forming you that you can t get an estimate of th
7. distributed by the authors 28 6 KNOWN BUGS 6 1 Bug one The most common bug is related to the coordinates import from an ASCII file As we said you can select the column where the coordinates are Tabulations or spaces are interpreted as column separations therefore if there are labels preceding X Y coordinates you must be sure that this labels do not contain spaces in them In the example 1 below you can see how h bels containing spaces Hong Kong amp New York affect the import detrmining a column shift in coordinates import The way out is to replace these spaces with underscores or by de leting the space Hong_Kong or HongKong or Hong Kong etc In this way the im port is correct and X Y coordinates of all the samples appear in the same column Example 1 Original ASCII FILE Hong Kong 52 London ZS al Paris 21 Madrid Ve and how it will be read Column l Column 2 Column 3 Column 4 Madrid 2204 Example 2 Modified ASCII FILE and how it will be read Column Column 2 Column 3 Column 4 ae ae ee London 23 jae i e E Paris 2a Madrid e da U y To import the coordinates you just have to start the import at column 2 trough the setting pa rameters visible in Fig 6 since the software is unable to read labels and automatically num bers samples starting from 1 29 6 2 Bug two The second most common bug appears when there a
8. edge that drives the boundary towards that triangle of the two possible ones that is associated to higher distance measures If identical dis tance values are observed again then the barriers is stopped this phenomenon is called undetermined direc tion in the report see how a report looks like in Fig 20 10 NOTE that the order of the samples in the X Y coordinates file has to be the same as in the distance matrix or vice versa Figure 14 see follo wing page Example concerning the linguistic diversity of the province of Ferrara Italy 16 towns have been studied and a linguistic distance matrix computed All the different sub figures A B C D E F G H exemplify the computation of barriers with the Monmonier 1973 algorithm The Delaunay triangulation is shown in green the Vorono tessellation in blue samples are in red and virtual points in light blue Note that the barriers lie on the Voronoi tessellation A Distance values are associated to triangulation edges The computation of the first barrier a starts from the edge associated to the higher distance value the one between samples 5 and 6 that has a distance value of 65 B The extension of the first barrier a continues across adjacent edges In one direction left the ex tension of the barrier stops since the limit of the triangulation is already reached then the extension proceeds in the other direction across the edge
9. it can be read by all image editors Because the quality of a pixelized image depends from its size when selecting the BMP export option you can adjust the width the height and the resolution in a dialog box Fig 40 The creation of a BMP image can be time keeping with high resolutions Image size Print Size Pixel Dimensions Width 21 i Jem Width eon pixels Height a4 em Height 358 pixels Resolution 36 dpi Figure 40 Setting window that opens when exporting or printing a BMP image By these parameters you can select the resolution and the print size of the print 5 5 2 Printing directly from the program You can print your map directly from the program without exporting it previously To print select the Print option from the File menu Soon after the same dialog box described for the export of BMP images opens Fig 40 this dialog box enables you to select correct pa rameters for the print HOW TO CITE There is one article describing the software with some application examples F MANNI E GUERARD amp E HEYER 2004 Geographic patterns of genetic morphologic linguistic varia tion how barriers can be detected by Monmonier s algorithm Human Biology 76 2 173 190 Additionally you can cite this manual F MANNI amp E GUERARD 2004 Barrier vs 2 2 Manual of the user Population genetics team Museum of Mankind Musee de l Homme Paris Publication
10. resampled boot strap matrices you have if you want to perform a multiple matrices analysis See section 4 Robustness of barriers With this box you have to say to the program what are the separators 1 concerning the line of the data file where the import has to be started Start import at line 2 the column of the data file trom which the import has to start Start import at column 3 the number of text lines that can also be empty lines between matrices if you are analyzing multiple matrices Lines between ma trices With this box you can select which matrix you want to preview before the extrac tion This option is useful to check if multiple matrices data will be correctly imported 14 Figure 19 Alert message appearing when you are attempting to com pute classic Monmoniers analysis on a single matrix on mul tiple matrices data Impossible to perform baniers significance best on a single matrix Monmonier Barrier Report Fig 20 3 Example of barrier text re port where 10 barriers were computed You can see how barriers are computed and in what directions In the ex ample barrier 1 starts on the H He Creating single monmonier layer mati50 xxx Parameters Harrier count 10 Loading distance matrix n 1 Constructing barrier n 1 layer matlS0 matrix n 1 Beginning of barrier gt segment 209 8
11. satisfactory when the swarm of points approximates a convex polygon or modify them by adding deleting and or moving virtual points Another way to obtain a satisfactory map tessellation triangulation is to delete all the virtual points and to add new ones You have the Delete all virtual points option in a menu appearing when you click the right button of your mouse Any kind of virtual points editing influences the shape of the Voronoi tessellation and of the triangulation Virtual points often lead to the destruction of an edge of the triangulation between two samples that are located at the border of the map This is the case when the spa tial distribution of samples does not correspond to a convex polygon meaning that there is concavity in the shape of the swarm of points see Fig 9 Where concavity is there you will find long edges connecting samples at the two extremes of this concavity Concluding when you don t want far samples to be considered as adjacent because they are not geographically neighboring you can separate them by appropriately placing some virtual points thus obtaining a Vorono tessellation Delaunay triangulation responding to your needs All this discussion on the virtual points will appear more focused once that you will get familiar with barrier computation Check also section 3 2 gain on the use of virtual points 2 2 2 Modification of the map The graphic menu Tools the third of the second line o
12. 4 distance 8 818 Constructing barrier first direction segment 84 46 distance 7 edge connecting populations segment 4 170 84 distance 7 612 u n segment Bd 1 distance 7 532 209 and 84 209 sat segment 76 9 distance 7 that is associated to a dis tance value of 8 818 that Reached end of barrier stop Constructing barrier opposite direction segment 209 12 distance seqment seqment seqment segment segment segment segment segment segment segment segment segment segment segment segment segment zegment zegment zegment seqment segment segment segment 171 171 160 160 115 23 23 eS 164 169 169 169 121 195 apes 168 158 172 Lie 200 162 162 174 12 160 159 115 29 29 145 129 129 164 33 35 35 35 47 A 172 146 123 123 123 174 Yay distance distance distance distance distance distance distance distance distance distance distance distance distance distance distance distance distance distance distance distance distance distance distance is the higher distance value in the triangulation Then you have all the edges of the tri angulation crossed by the barrier until it stops Barriers when Starting in the middle of the triangulation are amp tended in two directio
13. AP 5 1 Layers A BARRIER vs 2 2 map results from the superposition of different layers concerning the the dots original points marking the geographic position of samples populations the dots corresponding to virtual points the labels of the points automatically numbered starting from 1 Voronoi tessellation the edges of the Delaunay triangulation the barriers the labels of the barriers the bootstrap score in case of multiple barriers CON NM AKRWND You can choose which layers have to be displayed by selecting the Layers scroll down menu and selecting deselecting the different layers Fig 26 The choice is visualized in the button menu in the Active layer box on the left of Fig 27 and by the closed 4 or open eye 8 as we will see in the next paragraph Triangulation Editor 6Points dvt File Edit Layers Jools Points oom M Active layer Tools j OriginalPoints doi J8 3 VirtualPoints 3 Labels Delaunay Voronoi show all layers Hide unactive layers Figure 26 Scroll down window corresponding to the Layers menu You can choose to show or hide any layer by this menu Additionaly you have fast buttons in the Active layer graphic menu visible in figure 27 Triangulation Editor 6Points dvt File Edit Layers Tools Points o00m Active layer Properties Tools KARRERAK Figure 27 The main command bar of the program Detailed descriptions o
14. Manual of the user version 2 2 Etienne Gu rard Franz Manni MNHN 2002 The software was developed to visualize the effect of any pa rameter change in real time This function that makes unneces sary any manual refresh requires a good graphic card support ing OpenGl rendering The software is optimized to work with M Windows 95 following versions but some bugs may happen since almost each Windows version differently handle the dif ferent software functions April 2004 Manual version 1 0 TABLE OF CONTENTS 1 INTRODUCTION 1 1 What kind of map you will obtain 1 2 1 Delaunay triangulation and Voronoi tessellation 1 2 2 Cuircumcircle property of the Delaunay triangulation OBTAINING A MAP 2 1 Importing coordinates 2 2 The map 2 2 1 Why virtual points are necessary 2 2 2 Modification of the map COMPUTATION OF BARRIERS 3 1 Setting the parameters for matrix matrices extraction 3 2 Again on the use of virtual points ROBUSTNESS OF BARRIERS 4 1 Additivity of barriers 4 1 1 One barrier computed N times 4 1 2 Two or more barriers computed N times 4 2 Using BARRIER vs 2 2 in the reverse mode VISUAL DISPLAY OF THE MAP 5 1 Layers 5 2 Levels of undo 5 3 Visualizing barriers 5 4 Real time analyses and the synchronization with the interface 5 5 Saving exporting and printing the results 5 5 1 Exporting a pixelized image 5 5 2 Printing directly from the program HOW TO CITE KNOWN BUGS 6 1 Bug one 6 2 Bu
15. change the geometry of the barrier data not shown This discussion about virtual points is an addendum to the section 2 2 The map Figure 21 See text in this page 10 oA NORDCCAN ARABS ge Sn ee N se aM err Figure 22 Human Y chromosome differences around the Mediterranean basin A Delaunay triangulation thin dot ted green lines and the first genetic barrier Solid red line computed on a Fst distance matrix between populations ae shown redrawn from Manni et al 2002 Human Biology 74 645 58 Note that the edges between Moroccan Berbers and Saudi Arabia populations as well as between France and Georgia were deleted from the published figure The final Voronoi tessellation and Delaunay triangula tion was obtained by editing the map by a suitable placing of virtual points 17 4 ROBUSTNESS OF BARRIERS The definition of the Monmonier s algorithm reminds the dichotomic process of arborescence of phylogenetic trees once a barrier passes across the edges of a triangle it can be extended only across one of the two remaining edges in what we will define a right or left decision see section 3 Computation of barriers To assess the robustness of computed barriers we have implemented a test that is based on the analysis of resampled bootstrap matrices for ex ample from molecular sequences As with bootstrap phylogenetic trees a score will be asso ciated to all the differe
16. cribed to this triangle If we compute all the triangles that have a circumscribed circle whose centre is a Voronoi vertex we obtain the Delaunay triangulation Fig 4 Concluding the Delaunay triangulation can be ob tained from the Voronoi tessellation and vice versa Delaunay triangulation is the fastest triangulation method to connect a set of points localities on a plane map by a set of triangles Figs 2B 3C It is the most direct way to connect triangulate adjacent points on a map Given a set of populations whose geographic locations are known there is an only possible Delaunay triangulation k rs a RE Figure 3 A B C D A Sample points Samples populations in red and corresponding Voronoi tessellation in blue B Two points are neighbors if the have a common edge in the Voronoi tessellation C Sample points samples populations with corresponding Voronoi tessellation in blue and Delaunay triangulation in green D The circumcircle property Given a triangle of the Delaunay triangulation the segments of the Vo ronoi tessellation crossing his edges will join in a point that is the center of the triangle 1 2 2 Circumcircle property of the Delaunay triangulation The Delaunay triangulation of a set of geographic locations Fig 2B is constituted of trian gles satisfying the following property the circle circumscribed to each of such triangles does not contain any point of the triangle except its vertexes Fi
17. dentify the rank of barriers but this information is impossible to be displayed for hun dred of barriers without generating a chaotic representation Also because barriers can have different geometries and can be composed of a variable number of edges 18 To solve this problem we have implemented in the Barriers scroll down menu an op tion called Barrier selection Fig 34 that allow you to visualize only the barriers of a cer tain rank Let s imagine you computed 5 barriers on 100 bootstrap matrices With the box Barrier selection you can check the numbers 4 and 5 thus seeing only the 100 barri ers computed in as the fourth and fifth and masking the first three ones By plotting different images separately you will visualize only the barriers of different orders It must be under lined that in this way any additivity is lost because as hown in figure 9 barriers can stop one against another a barrier of the 3 order can stop against a barrier of the 1 order etc and by plotting them separately this phenomenon can t be visualized Besides this inconve n ience the option is useful to provide a deeper understanding of the results Figure 23 See description in the following page 19 Figure 23 Example of barrier computation with multiple matrices Let s assume that we have 26 populations spa tially spaced as visible in the figure and that we have 4 matrices accounting for them usua
18. e level of significance of with sub replicate analysis If you have a multiple matrices data file the Yes box will be automatically checked informing you that Sub replicate analysis will be performed This option is related to the creation of a text report giving all the details of barrier com putation step by step Fig 19 Tabbed C Lethe E LEi Mame fraticext epi 13 Load matric data Bym probleme mat exempel matsl ext Figure 17 Dialog box enabling you to select the ASCII file con taining the matrix matrices for barrier computation d mat_holande lt 3 Mate Spirale20000 a mat_hallandet E aiima thread out fic The selection of the file containing the matrix leads e ll acres you to the dialog box shown in figure 18 Type Teste seulement Taille 399 Ko ea ST Isp ima iss i taj Armada Import distance matrices File preview Data preview O0000 Zee cll Ser ee 14094 ae fa Importing data from file Cw INN T Protiles 4dministrateurnshMes documents mat S0 bet Matrices Matrix size 7 93118 W Square matris M0 Oo n 0 N Be Oo d Fe ie cd Boe Ea eh 47969 96941 tae Eke KARBA eee 54675 aoe ve LARGE Soh eek 09201 a J J Oo 493118 Foi 5 14094 fF TTS 4 7969 r 46941 o ar 602 oS Ff oose O 7 09981 r 5242 F595 F ooF a4 20132 6 00856 r 6517 r a r065
19. e where you click Displays a larger portion of the map centered on the zone where you click Map frame moving Moves the map in order to make visible areas that are not visible on the screen Iriangulation Editar 6Points dvt Fle Edit Leyers Toole Pointe Zoom ichalgei reas Teck ennom peum wi nr eeaag a Fig 12 Specific edges of the triangulation can be selected See the grayed flashing motif in the figure and then deleted This deletion causes the loss of the triangle to which the edge belong NOTE that populations are automatically numbered starting from 1 according to their rank in the coordinate data file No other labels will identify them 3 COMPUTATION OF BARRIERS Once a network connecting all the localities is obtained and a corresponding distance matrix is available the Monmonier s 1973 maximum difference algorithm can be used to identify boundaries namely the zones where differences between pairs of populations are largest Even though BARRIER vs 2 2 automatically performs all the necessary computation it may be useful to describe the step by step procedure leading to the barriers 1 Before running the algorithm itself each edge of the Delaunay triangulation is linked with its corresponding distance value in the distance matrix 2 Starting from the edge for which the distance value is maximum and proceeding across adjacent edges we cross the ed
20. e you will find Dan RRS long edges connecting samples at the two extremes of this ERO ONS i concavity If you have convexity there are no long links as F net tity you can see in the figure 2 2 The map Once that the coordinates have been successfully extracted Barriers automatically computes a map that is displayed All the elements of the map can be modified for a better dis play and you will find all the details concerning these settings in section 5 Visual display of the map Before introducing the computation of barriers we will describe one of the main fea tures of Barrier software that is the possibility to edit the Voronoi tessellation and the I launay triangulation by the use of what we will call virtual points virtual samples popula tions As we will see a satisfactory definition of the borders of the triangulation can t be automatically obtained as it also depends on the requirements of the user For these reasons a triangulation editor has been implemented within BARRIER vs 2 2 2 2 1 Why virtual points are necessary In Voronoi _ tessellations the tessellation can t describe the borders of the mapped area since polygons enclosing the external samples to infinity Figs 2 9 This phenomenon results from the Voronoi division of the geometric space according to sample locations The compu tation of a Voronoi tessellation between two points results in two semi planes three points re sult in th
21. ee barriers of such figure are visualized in yellow Additionally data was also analyzed as mult ple matrices corresponding each to the phonetic variability of single word 24 different words were used in the survey With the superposition of the 24 first barriers one for all the 24 matrices we obtain the boundaries drawn in red whose thickness is proportional to the number of times a barriers passes there Please note that this example differs from the one of figure 25 in the sense that here we don t have bootstrap matrices but matrices accounting for the variability of different markers words in this case 21 Al ene 04 CaaS TRESS WL AAS BEEN MEO Sit a Figure 25 Surname differences in the Netherlands The analysis refers to the surname distribution of 226 locali ties Differences were summarized in a single overall distance matrix used to compute the first five bar riers with the Monmonier s method yellow lines We also analyzed the first five barriers in red on 100 bootstrap matrices obtained by randomly resam pling original surnames The thickness of each edge of the barriers is proportional to the rumber of times it was included in one of the 500 computed barriers In green the Delaunay triangulation in blue the Voronoi tessellation Small blues dots outside the triangulation are the virtual points used to close the Voronoi tessellation see text 22 5 VISUAL DISPLAY OF THE M
22. els Delaunay barriers since you may work on different Voronoi matrices related to a same triangulation X Barriers Barrer title you can select the matrix with an additional g multiple _barriers sub menu appearing in the Layers menu Show all layers Barrier title and Barrier numbers layers Hide unactive layers Options are available in the same way C Figure 33 Layat a a i Let s imagine we have two files containing open bey ah a lin n l i e ce Stovall ma data single_barriers and mult Hide unaetive ple_barriers These files are visualized in Hda the Barriers scroll down menu The active Remove all ennha layer the one you can modify is discernible multple_borriers since it is checked vandaar 25 sere Figure 34 Continued from figure 33 Zoom Barriers 7 To activate the fnultiple barriers file and 7 New a therefore to be able to modify the properties Se of the corresponding barriers numbers ioe pares color thickness etc you have to click on SS a the activate option at the beginning of a 7 aine hamers F scroll down menu visible in the figure on the iple bamiers TN Activate very right Status window t Configure _ Barrier selection Hide barriers Hide labels Foreground Move front Move back Background Summarizing for each barrier layer that is for each matrix used to co
23. f barriers to be computed A barrier is supposed to highlight the geographic areas where a discontinuity exist meaning that populations on each side of the barrier are more similar than populations taken on different sides of the boundary As a consequence you expect the barrier to cross those edges of the triangulation that are linked to the higher distance values of the matrix In the ideal case barriers cross the edges associated to these values regularly decreasing from the higher to the lower values being barriers of the late orders associated to lower values than barriers of higher orders This hardly ever happens We could say that you can always com pute the first barrier without taking big risks since the first boundary is the most important one Nevertheless also subsequent boundaries can be as much interesting especially if there Not all the values of the distance matrix but only those values that appear in the triangulation according to an adjacency criterion 20 are many populations in the map In a certain sense the bootstrap procedure we advocate for barriers 1s a way out since until barriers keep a similar pattern flowing matrix after matrix a pattern do exist The reverse is also true when barriers do not exhibit a recurrent pattern and flow in all directions you don t have a pattern Figure 24 Dialect differences of the Province of Ferrara This example refers to the same data of Fig 14 here the first thr
24. f the graphic menus are provided at pages 8 and 24 The visualization of the map can be modified by changing the color and the width of the i Delaunay triangulation ii of the Voronoi tessellation and iii of the barriers Moreover the color and size of iv sample points and v of virtual points can be modified Finally all the at tributes of vi population labels can be modified All these changes can be done by selecting 23 the Active layer button on the menu bar and with the Properties box options that are lo cated on the bottom of the menu bar When some properties are not available for a given vart able the corresponding button is displayed as grayed The eye can wide of shut When it is open red in the center like in the picture on the left it means that a given layer is visible on the screen If you want don twant to see some thing you have to select the corresponding active layer and then to click on the eye until the layer appears disappears Button leading to a palette of colors that can be selected to change the display proper ties of the different layers Fig 28 This button as active with all layers Button to set the width of Voronoi tessellation edges and or of Delaunay triangulation edges Fig 29 This function is disabled when other layers than those specified are se lected Button to set the size of sample points and or of virtual points Fig 30 This function is disabled when other layers than th
25. f the top menu bar is made of 7 buttons that enable the navigation and the modification of the map Selecting an object With this button you can select a specific edge or population of the map that will then be ds played by a flashing motif Fig 12 Even though all the elements of the map can be selected in such a way this option can be useful for presentations or didactical purposes only the edges of the triangles and the virtual points can be deleted once they are selected selection by the arrow and then Del key It must be noted that the suppression of the edge of a triangle leads to the Suppression of the triangle to whose such edge belongs Moving a virtual point To move a virtual you must select the arrow shown on the left and click on the virtual point you want to move By keeping the left button of the mouse pressed you can then move the point as you want Adding a virtual point Adding a virtual point is simple you just need to select the arrow on the left and click on the screen in the position where you want such point to be added Soon after the Delaunay tri angulation and the Voronoi tessellation are recomputed Deleting a virtual point To eliminate a virtual point you must select the arrow and click on the virtual point you want to suppress Also in this case the Delaunay triangulation and the Voronoi tessellation are e computed Displays a narrower portion of the map centered on the zon
26. file data to be extracted In the central window Data pre view you see what kind of extraction will result Such parameters are bcated on the right part of the window Extraction settings are 1 the option concerning the line of the data file where the import has to be started Start import at line 2 the option concerning the column of the data file from which the import has to start Start import at column 3 the number of points Samples populations that will be used to obtain the Voronoi tessellation and Delaunay triangulation Number of points 4 the or der of coordinates in colons that can be X Y or Y X Data order Computing Figure 9 corresponding to paragraph 2 2 Figure 7 Box informing you that the coordinate extraction went wrong Pos sible causes can be a wrong definition of extraction parameters or an careless prepared input file See section 6 Known bugs to fix most common bugs Figure 8 Box that opens during the extraction showing the progress bar If you see this window it means that things are going well Virtual points often lead to the destruction of an edge of the triangulation between two samples that are located at s LINEN IEN the border of the map This is the case when the spatial ATOE 3 distribution of samples does not correspond to a convex IS SSE RE polygon meaning that there is concavity in the shape of D TATERAO the swarm of points Where concavity is ther
27. ftware To compute the barriers once a map has been created you have to select the New option from the Barriers scroll down menu on the top command bar Fig 15 Initially you have to select the file contaming the distance matrix or the distance matrices as we will see later corresponding to the populations displayed in the map to this end you must click on the Load matrix data button visible in Fig 16 that opens a standard operrfile dialog box Fig 17 Once that you have selected the ASCII file containing the matrix or the matri ces a second dialog box called tmport distance matrices will appear With this dialog box Fig 18 similarly to what was done when creating the map you will set parameters to cor rectly import the matrix This window is divided in three parts 7 on the left a view of the file containing the matrix or the matrices ii in the middle a preview of the data as they will be extracted according to setting parameters and on the right iii the parameters for matrix ma trices extraction Once that a matrix is imported boundaries will be displayed according to the setting of the Monmonier algorithm specifications box Fig 16 See captions of figure in this page for more details Figure 15 a E To start barrier computation you first need to open a barrier project and to import a distance matrix or Hile uractive multiple distance matrices from an ASCII file
28. g two ADDENDA Page AUN CONN AN 18 18 18 18 20 23 23 25 26 27 28 28 28 29 29 30 31 1 INTRODUCTION When sampling locations are known the association between genetic and geographic dis tances can be tested by spatial autocorrelation or regression methods These tests give some clues to the possible shape of the genetic landscape Nevertheless correlation analyses fail when attempting to identify WHERE genetic barriers may exist namely the areas where a given variable shows an abrupt rate of change To this end a computational geometry ap proach is more suitable since it provides the locations and the directions of barriers and it can show where geographic patterns of two or more variables are similar In this frame we have implemented the Monmonier s 1973 maximum difference algorithm in a new software in order to identify genetic barriers To provide a more realistic representation of the barriers in a genetic landscape a sig nificance test was implemented in the software by means of bootstrap matrices analysis As a result i the noise associated in genetic markers can be visualized on a geographic map and ii the areas where genetic barriers are more robust can be identified Moreover this multiple matrices approach can visualize iii the patterns of variation associated to different markers in a same overall picture This improved Monmonier s method is highly reliable and can also be applied to no
29. ge of the triangle whose distance value is higher 3 The procedure is continued until the forming boundary had reached either the limits of the triangulation map or another preexisting boundary In principle barrier construction can be continued until all the edges of the triangulation are crossed by a barrier but it must be noted that the significance of barriers is expected to crease with their rank We did not have the time to implement a statistical test to assess if bar riers pass by the edges of higher ranks and this implementation represents one of the possible future improvements Fig 13 Three examples of barriers with different geometries Barrier 1 closes itself in a loop around a population Barrier 2 stops against a previ ously computed barrier Barrier 3 has an independent and linear extension More details concerning the bar rier computation procedure are provided in the next figure gt The computation of barriers can be difficult when identical distance measures appear in the distance matrix have since in this case the cited right of left decision can t be made The way out suggested by Barbujani et al 1996 in Human Biology 68 201 205 to include in the barrier the edge associated to the shortest geographic distance may be not appropriate since it implicitely assumes the IBD model even when it was not tested We undertook a more conservative approach by including in the forming barrier that
30. gs 3D 4 Let s consider now a triangle where C is the center of its circumscribed circle By definition C is equidistant from such vertexes being its distance equal to the radius Fig 3D Since only the vertexes belong to the circle all the points constituting the triangle will have a distance from C that 1s minor than the radius length This trivial geometric property enables us to define C as the vertex formed by three Voronoi edges that belong to those Voronoi neighborhoods having the ver texes of the triangle as centroid As we said Voronoi tessellation edges are located on the medians of the edges of the triangle A Voronoi tessellation is obtained from the intersection of the medians of the triangles defined in the Delaunay tessellation Figure 4 Circumcircle property in this example we show circles cir cumscribed to the triangles highlighted in light blue The circle circumscribed to each of such triangles does not con tain any of the points of the triangle except its vertexes Brassel K E and D Reif 1979 A procedure to generate Thiessen polygons Geogr Anal 325 31 36 4 2 OBTAINING A MAP 2 1 Importing the coordinates The user can obtain a triangulated map from the X Y coordinates of the original points loca tion of samples populations etc These coordinates should be made available as an ASCII file txt built as in the example 2 of section 6 Known bugs To import the coordinates select the
31. ing in H we have also provided a visualization thin blue dotted lines of the additivity of barriers by showing that the number of barriers flowing in a given section between two arbitrary points is equal to the total number of computed barriers that is to the number of matrices As we said in the text this property is easily visible only when you compute the first barrier of each matrix and when barriers do not close themselves in a loop 4 2 Using BARRIER vs 2 2 in the reverse mode How _ many barriers should be com puted In all the preceding pages we have described a classic barrier computation with a limited number of boundaries It can be of interest to see if there are areas of the map where barriers are less likely to appear or never appear at all until the maximum number of barriers 1s com puted Even if this use of the Monmonier algorithm is unconventional it can useful to get an idea of the most homogeneous and the most diversified areas of the plot The first question we never addressed before is How many barriers should be computed The answer is not obvi ous therefore we will provide a discussion concerning such question more than a definite sponse First of all given the nature of the algorithm you can compute as much barriers as there are populations In this case in the end each population will be surrounded by barriers This kind of representation is obviously meaningless and so comes the question about the number o
32. ing barriers please wait Sa Sa Figure 35 Figure 36 Progression bar displayed during the matrix Progression bar displayed during barrier com reading preliminary to barrier computation putation 20 5 5 Saving exporting and printing and the results The specific extension of Barrier files is dvb Delaunay VoronofBarriers The icon of the software represents a level crossing sign Fig 37A The dvb files are dis played by the same icon on a background representing a sheet of paper Fig 37B Results can be saved as specific DVB files File scroll down menu Save option A possible problem can be represented by the size of data as an example a dvb file account ing for 226 samples and 100 resampled distance matrices as in the example of Fig 25 weights about 40 Mb Those familiar with bootstrap matrices know that it is not uncommon to have 100 or even 1000 resampled matrices to be analyzed meaning files of 40 or 400 Mb To improve software performances not all the matrices will be loaded in memory see Fig 35 but whenever the user will move add delete a virtual point all the matrices will be read again If there is not enough space on the local drive an alert message appears Fig 38 Figure 37 A B A Icon of the software Barrier B Icon of Barrier files Figure 36 Hes enoet snae ar Ai damnet Aare Message box that pops up when the DVB file is too Please select a vaidfiedive aaa
33. lly bootstrap matrices are available in much higher numbers this is only a simple and didactical example Let s also imagine that we ask the program to compute four different barrier projects each one consisting of the first barrier on each of the four different matrices thus obtaining the four maps shown as A B C and D If we superpose these maps we obtain the map shown in E where we can show on each edge of the Voronol tessellation the number of times the four barriers pass by there small numbers in E We can now plot the thickness of these segments proportionally to such numbers as was done in F When YOU run BARRIER vs 2 2 ON Multiple matrices you will obtain this kind of representation In this example intentionally barriers show a very similar pattern and pass in a Same up down direction thus suggesting that a pattern do exist and that the four matrices support it Now comes the question of how these results should be presented 1 They can be presented as in E thus leaving to the reader the interpretation of the patterns 2 you can provide a spatial range where all the barriers or almost all pass as in G or 3 as in F you can keep only those edges supported by bootstrap scores higher than a given cut off value in this case 2 that is the 50 This last choice can be controversial because it is preferable in our opinion to visualize all the barriers in order to avoid oversimplification Conclud
34. meters is changed the pre view of the extraction is updated Once that the parameters are correctly defined you must confirm your choice by OK Fig 6 Soon after the software verifies if all the coordinates are numbers and if there is Y value for each X value and vice versa If an error is detected an alert message appears Fig 7 If the coordinates are successfully read by the software Fig 8 then an extraction bar appears displayed and the triangulation map is computed and displayed The triangulation time pends on the number of coordinates Triangulation Editor 6Points_dvt q File Edit Layers Tools Points oom New Ctrl N Tools Open Ctrl O Close Ctrl F4 Dave Ctri Save as Export Printer setup Print Ctrl P Quit Ctrl Q Figure 5 To open a coordinate data file choose New from the File menu To open an existing project choose Open Import coordinates data Importing data from fle C AWINNT Profiles dministrateur Mes docume File preview m m g m m pl 1 3 4 5 6 H Figure 6 Data preview 0 999921 044 0 01 256606 OSS 8E 00251 301 54 O SSS28S465 00376027 O SS67 36951 005024443 0 9560 2671S 0 0627 90656 O OFS326381 0 9961 33591 0087851401 O SS4550S9920 100260S4 a The Dialog box that opens when you are extracting X Y coordinates from a data file In the File pre view window left you have a view of the
35. mpute barriers a spe cific submenu is created in the Layers option of the menu bar The selection of a specific submenu makes possible the adjustment of corresponding barrier settings The command Activate enables the selection of the barrier layer of interest without passing through the menu Layers or the palette Active layer The command Configure enables the setting of the parameters of the Monmonier s algo rithm by visualizing the specific dialog box Monmonier algorithm specifications Fig 16 5 4 Real time analyses and the synchronization with the interface As we have seen the software makes possible the modification of the map shape This func tion implies the editing adding deleting or moving of virtual points This kind of editing modifies the adjacency matrix related to the Voronoi tessellation as a consequence since the barriers pass on the edges of the Voronoi tessellation it is necessary to totally re compute the barriers after each virtual point editing If you find that barrier re computation takes too much time elapsed time is visualized by progression bars as in Figs 35 and 36 since a real time analysis 1s performed after all change we suggest you to arrange the geometry of virtual points before computing barriers Barrier status controler Barrier status controler Creating layer totaleOQ_ 49 Creating layertotaleOQ_ 49 Sorting matris data please wait Construct
36. n genetic data whenever sampling locations and a distance matrix between corresponding data are available 1 1 What kind of map you will obtain To obtain a geometrically satisfactory map from a list of geographic X Y coordinates Fig 1 we have implemented in the software a Voronoi tessellation calculator From this tessellation Fig 2A a Delaunay triangulation is obtained Fig 2B In the following section we will provide some geometric background intended to describe the properties of this approach Figure 1 Example of sample points the X and Y locations of chief towns of French departments Monmonier M 1973 Maximumdifference barriers an alternative numerical regionalization method Geogr Anal 3 245 61 Mind that the software can handle only X Y coordinates format and not as longitude and latitude coordinates 2 1 2 Some geometric background 1 2 1 Delaunay triangulation and Voronoi tessellation The Voronoi tessellation represents a polygonal neighborhood for each sample population that is constituted of those points on the plane that are closer to such sample than to any other one Figs 2A 3A This tessellation determines which samples populations are neighbors adjacent As a consequence two samples A and B are adjacent if the correspond ing Voronoi polygons have a common edge Fig 3B All the points on such edge are equi distant both from A and B and the edge itself is the median of the segment AB
37. ns and you have the details of his process in the construct ing barrier opposite direction section Barrier 2 starts with the edge con necting populations 196 and ma ca a ea ea a ea a oa a oa a a a ee a a oS a a a aa OO A DO I I HI I HO 178 196 178 that is associated to a dstance value of 8 485 that Is the higher distance value in the triangulation of those not d ready concerned by the passing of barrier 1 As you can see from the buttons be low the report can be saved as an ASCII file segment Yo 19 distance Reached end of barrier stop End of barrier flatriz n i1 HHH Constructing barrier n 2 layer matisi Beginning of barrier segment 196 178 distance 6 4865 Constructing barrier first direction segment 192 178 distance segment 178 114 distance segment 178 109 distance o 321 0 336 0 138 3 2 Again on the use of virtual points In section 2 Obtaining a map we discussed the use of virtual points mainly in terms of map shape Now that we have described how to obtain the barriers we will discuss how the use of virtual points samples population can influence barrier computation As we said virtual points Fig 21 A B locally modify their neighborhood being interpreted as the borders of the triangulation Their appropriate placement is of great importance since the more external edges of a V
38. nt edges that constitute barriers thus indicating how many times each one of them is included in one of the boundaries computed from the N matrices tipically N 100 The scores are visualized by representing the thickness of each edge proportionally to its bootstrap score Fig 25 In other words if you have 100 matrices and you want to com pute the first barrier you will obtain 100 separate barriers These 100 different barriers dif ferent in the sense that they have been computed on different matrices are displayed in a sin gle picture by plotting the edges of the Voronoi tessellation proportional to the number of times they belong to one of the 100 barriers check a simpler example in Fig 23 If a given pattern exists then you should obtain barriers repeatedly passing in certain areas of the plot If barriers pass everywhere in the plot then your results may be not robust in terms of geo graphic differentiation This issue is similar to the interpretation of phylogenetic trees boot strap scores and similar comments can be applied to barriers 4 1 Additivity of barriers In bootstrap phylogenetic trees each node of the tree is supported by a score S with 1 lt S lt N where N is the number of resampled matrices Using bootstrap matrices with the Monmonier algorithm results in some additivity properties that depend on the number of computed barri ers Let s consider now the simpler case of the computation of a single barrier 4 1 1
39. of the triangulation between samples 4 and 6 that has a distance value of 56 the second higher distance value of the triangulation The extension of barrier a continues by crossing the edges that have higher distance value until the limit of the triangulation is reached edge between 2 and 13 distance value of 46 F If the procedure is continued as itis here the case you will then start the construction of the second barrier b Between all the edges that have not been crossed by the first barrier a the one associ ated with the higher distance value of the matrix is 58 distance between points 14 and 16 This edge is the starting point of the second barrier b See Fig 14 G G As with barrier a the extension of the barrier b is continued until the two extremes reach the limits of the triangulation as it is again the case here or close on themselves in a loop or reach another barrier F A third barrier c is computed note that this barrier is constituted of a single edge since on one di rection the barrier immediately reaches the limit of the triangulation and on the other direction It joins a pre existing barrier 11 12 3 1 Setting the parameters for matrix matrices extraction Now that the kernel of the Monmonier algorithm has been fully presented we will introduce the practical computation of barriers by using the so
40. oronoi tessellation will tend by definition to infinity Fig 22B It often happens 15 that one of such Voronoi edges corresponds to a triangulation edge that is coupled with the highest genetic distance value of the matrix Therefore the origin of the barrier will take place outside the triangulation itself In figure 21 we compare the first five barriers after A and before B adding the virtual points that close the Voronoi diagrams Any further triangulation program that doesn t correct for this geometric property of Voronoi diagrams is likely to drive to fake barriers when the Monmonier s algorithm is applied to it Concluding by editing the triangulation the user adapts the Dealunay network to spe cific features of the geographic space as for example the presence of deserts or lakes More over this tool can be useful to delete some long links between distant populations These long links appear between external samples when the general shape of the triangulation is not con vex Fig 9 since they will be visualized as adjacent by a Voronoi tessellation An extreme case of external links removal is provided in figure 21A where all the triangulation lies in side the administrative borders of The Netherlands and only links between very close neighbors were preserved A further example is shown in figure 22 here the long link be tween the French and the Georgian samples was removed in this case its presence or absence doesn t
41. ose specified are selected Button to set font properties size style of sample labels and of bootstrap scores in multiple matrices analysis Triangulation Editor 6Points dvt meig Figure 28 Pila Edt eee on Color palette enabling you to display all Properties i lea p or ys the different layers composing a map by BH se A k amp i l l l i different colors This palette is accessible only through the 8s button in the Prop erties command bar cire ler Tools D File Edit Layers Tools Points Zoom File Edt Layers Took Points Zoom Arte bia a e i Tak inke lapsi Papa Took ar a le ce ee ea a E pereg od WA kek RE QAR 1 pt Lt 2 pts 2 pts 2 pta 3 pts 4 pts 5 pts 5 pts 6 pts 5 pts T pts T pte E pts re pts 9 pts O eeeeanetr E 10 pts 12 pts 1 pts 14 pis 14 pts 16 pts 18 pta 20 pts Figure 29 Figure 30 Line width palette enabling you to display Voronoi Palette enabling you to display population sample Delaunay and barrier layers with a different thick points and virtual points with a different thickness ness This palette is accessible only through the This palette is accessible through the button button in the Properties command bar in the Properties command bar 24 5 2 Levels of undo Obtaining a map with the desired shape by adding deleting moving vir
42. re samples having the same coordinates In this case the software can t compute a triangulation since the two points are superposed There are three possible solutions 1 To delete a population from the data 2 To merge the two populations in one single sample 3 To slightly modify the coordinates of one of the populations having the same coordi nates In the following example you have two populations having the same coordt nates London amp London2 causing a bug in the software The problem was solved by slightly changing the coordinates of one sample Problematic data Hong Kong 52 00 11 00 New_York 11 00 30 00 Paris aL 90 Ley OO Madrid 2A 00 14700 Modified data Hong_Kong 52 00 11 00 New_York 11 00 30 00 Paris Zi DO 18 00 Madrid 22 00 14 00 30 7 ADDENDA What must be said in the MATERIALS AND METHODS section of a scientific article if you want to publish maps obtained with BARRIER vs 2 2 The purpose of this section is to provide a checklist to help in the preparation of your article 1 You should say if some e external or internal edges of the triangulation were dele ted and justify this choice Mind that aesthetic purposes are not a justification 2 You have to say how many barriers you have computed and number them on the map 3 If you have analyzed multiple matrices bootstrap matrices say how many matrices were analyzed and compare these results with those obtained with a single overall ma
43. ree semiplanes etc AS a consequence only internal points are inside a closed po lygonal tessellation whereas peripheral points do not The Voronoi tessellation of peripheral points samples populations tend to infinity meaning that an adjacency is established also between some points that are not adjacent on the map itself Fig 9 The result is that in the Delaunay triangulation long edges will appear between very distant populations and this property will affect heavily the computation of bar riers as we will see in chapter 3 Computation of barriers Figure 10 Figure 11 The same populations as in figures 2 and 9 af If your populations approximate a convex polygon ter the computation of Delaunay triangulation in the ideal case a circle by placing virtual points and Vorono l tessellation and the automatic you will not destroy any triangulation edge The placing of virtual points in order to obtain a geometry of the triangulation in this example closed tessellation enclosing all the populations mains unchanged if such virtual points are not By comparing this figure with figure 2B you will computed see that many external triangulation edges have disappeared as a consequence of the presence of virtual points When a new triangulation is obtained virtual points are automatically placed along the borders of the swarm of points as in Fig 10 if compared to Fig 2B You can keep them as they are their geometry is often
44. trix 4 If you were working on a matrix matrices having several null distances be aware that the performance of the Monmonier algorithm is likely to be poor NOTE that the authors are not responsible for the misuse of the software and for any wrong outcome With Barriers you can do a considerable number of analyses but to avoid any misunder standing there are a certain number of things that you can t do 1 You can t compute and apply an Isolation by Distance IBD regression model di rectly 2 You can t use vectors instead of distance matrices 3 You can t use a similarity matrix instead of a distance matrix We probably forgot to address a lot of important key points concerning BARRIER vs 2 2 future versions of the manual if any will probably be more accurate Paris March 23 2004 31
45. tual points can be quite tedious To make this operation easier the software has been implemented with infinite level of undos Fig 31 Figure 31 File Edit Layers Tools Pane foom Though the Edit scroll down menu eee short cut option is the combination of Redo Move point 3 Maj Ctrl Z keys Ctrl Z 5 3 Visualizing barriers Barriers are visualized as an independent For this reason three new menus have been added to the scroll down menu called Layers as well as three special buttons to the palette named Active layer It must be noted that given a set of populations and their triangulation you may have several distance matrices corresponding to such populations Let s imagine that you have two different matrix files one called single_barrier and another called multi ple_barriers Barriers corresponding to such matrices will be visualized as two separate lay ers therefore before being able to change the display parameters you will have to choose the active layer you are working on This choice results in and additional submenu as visualized in figure 33 where you have to check which kind of barriers you want to graphically modify Figure 32 File Edit Layers Tools Points Zoom Barriers The Layers scroll down menu enables the selection of the layer to be modified line width point size colors etc Concerning ee ae OriginalPoints co 23 18 h VirtualPoints Lab
Download Pdf Manuals
Related Search