numerous programs exist for identifying regions of homology or collinearity between two genomes , including pipmaker , mummer , forrepeats , reputer , adhore , grimm , blastz   and patternhunter .
programs designed to identify homologous regions by making sequence alignments ( such as pipmaker and blastz ) may excel at accurately finding high - quality short alignments , but not at piecing together and reporting larger genomic - scale homologies .
programs designed to work with nucleotide data may not work with peptide data , or raw positional information such as marker positions . with increasing numbers of genomes being sequenced
, it is becoming a more frequent task to identify very large , often multi - megabase , corresponding regions between two genomes .
these are frequently interrupted by insertions , deletions , or small inversions in one or both genomes , but can nevertheless be considered to have recognizable common ancestry and genomic context , and to show approximate collinearity in gene order .
these large chromosomal regions that are similar in content and organization are frequently referred to as synteny blocks [ 4,10,13 - 15 ] or , in the case of a comparison of a genome to itself , segmental duplications [ 16 - 19 ] . here
we report two new programs , diaghunter and genopix2d , which are distributed together , and may be used together or separately to explore comparative genomic data at genome - wide or single - gene scales .
diaghunter has several strengths for large - scale collinearity prediction : it is cross - platform ( windows , unix , linux , os x , and others , requiring perl and the gd module ) ; it can easily and quickly handle large amounts of new genomic data ; it can operate on protein , nucleotide , marker , or other data types ; it includes bioperl and tcl / tk - based scripts for processing various input data formats ; and it generates simple text output consisting of lists of gene or nucleotide sequence or marker pairs and coordinates .
diaghunter identifies very large - scale synteny blocks - on the order of many megabases - despite high levels of background noise in the comparisons and despite large genomic discontinuities .
it is a ' lighter - weight ' program than most of those mentioned above , in that it does not carry out sequence alignments ( as do pipmaker , mummer , forrepeats , reputer , blastz and patternhunter ) . but its speed , low memory requirement , simple output format , platform portability , and flexible input format make it a worthwhile addition to the set of genome - exploration tools .
it also appears to out - perform the programs above in identifying extended , disrupted blocks as parts of larger features . while diaghunter is useful for identifying synteny blocks , it does not permit interactive querying of features in a genomic comparison .
genopix2d provides this function , allowing highlighting of groups of genes ( for example , synteny blocks found by diaghunter ) or sets of genes showing a specified level of similarity to two genes from the genomes being compared .
genopix2d ( a tcl / tk - based comparative , two - dimensional ' extension ' of the genomepixelizer software ) can also generate postscript output files of essentially any size , including query results and simple annotations added during a session of the program . as more genome sequences are completed , it becomes increasingly important for researchers to be able to reproduce and reanalyze reports of genomic comparisons .
it should also be possible to redo comparisons efficiently as genome assemblies are updated and reannotated .
for example , several seminal genome - scale comparisons of internal duplications in the arabidopsis thaliana genome have identified large internal synteny blocks , or segmental duplications ( for example ) , but depended on custom bioinformatics efforts and extensive pre- and post - processing tailored to the arabidopsis genome .
comparable predictions of segmental duplications in arabidopsis can be carried out using diaghunter on a standard , single - processor desktop computer in about 10 minutes if provided with parsed blast   data ( which can be generated in about a day , including the underlying blast analysis , with accompanying scripts ) .
the diaghunter / genopix2d distribution includes scripts that allow processing of genomic data from various input formats ( national center for biotechnology information ( ncbi ) genomic protein data sets , the institute for genomic research ( tigr ) pseudochromosome assemblies , or ensembl   gene queries ) , to produce finished images and predictions of synteny blocks .
diaghunter has been tested primarily with comparisons of predicted genes , but also works with dna or other comparisons that generate similarity matrices .
certain genomic material , such as comparisons of highly repetitive heterochromatic dna , present particular challenges , but comparisons between these regions can be masked and excluded from the analysis .
the output of diaghunter is in the form of text files and png ( portable network graphics ) image files .
output includes two text files containing gene names and/or coordinates , and a detailed and a thumbnail png image for each chromosome - by - chromosome comparison .
blast hits above a specified threshold are shown in the image files , with direct repeats shown in one color and inverted repeats in another color .
predicted diagonals are highlighted and numbered . all chromosomes in one or more genomes can be run in a batch process . to view diaghunter predictions , as well as any other two - way genomic similarity comparisons
diaghunter is implemented in perl , and requires the bioperl   and gd.pm modules   for blast parsing and image generation , respectively .
diaghunter takes as input simple , tab - delimited , parsed blast ( or other similarity comparison ) text files .
although designed to work with protein sequences , the actual requirements are for a file of coordinates of similarity ' hits ' , hit strengths , and ( optionally but recommended ) strand orientation . a bioperl - based blast controller and parser that generate this format
first , collinear regions must , by their nature , produce diagonal features in a dot plot .
second , in genomic data , these features may be interrupted by gene losses or by insertions in one or both regions .
third , there may be background noise in the form of homologies outside of collinear regions - such as local gene duplications , or high - copy gene families .
the algorithm deals with these characteristics by looking locally for the best diagonal candidates , compressing the search matrix to reduce the span between hits in diagonals , and heavily weighting against purely vertical or horizontal steps ( which might cause a search to incorrectly follow a line of highly repetitive hits ) .
the collinearity - identifying algorithm of diaghunter works by walking through a pre - computed array of filtered similarity hits . at each hit
, it checks in the neighborhood for hits that might either be other members of ' direct repeats ' ( forward steps in both genomic regions ) or ' inverted repeats ' ( opposite steps in the two genomic regions ) , choosing the nearest and most favorable positions first .
once a candidate diagonal has been initiated , only hits with appropriate combinations of orientations are considered ( if working with predicted coding - sequence data that include strand - orientation information ) .
the program follows these chains of best local diagonal steps recursively , checking up to 75 possible positions for each step in the vicinity .
each position contributes a score from a scoring matrix that gives the best scores to the nearest and most - nearly - diagonal hits .
a representation of the diaghunter scoring matrix is shown in figure 2 , where x represents the location of the ' hit ' at the current position in the search , and the area of the circles represents the preferred search order and score assigned to hits at any of these locations in the compressed hit matrix .
forward searches use the right - hand scoring matrix , and reverse searches use the left - hand matrix . at each step , a running - average score for the candidate diagonal is computed .
the program repeats the search to extend the current diagonal until a score threshold is passed or until no other candidate hits are located .
local gene duplications are added to the current diagonal and are removed from subsequent searches .
this helps to consolidate diagonals in which significant local duplications have occurred . if the diagonal meets the selection parameters ( numbers of hits in the diagonal , and average diagonal score ) then the diagonal is retained , and all hits picked up in this search are removed from subsequent searches .
the program then starts the search again from where the previous diagonal search was initiated .
if the sparse hits are brought ' closer together ' by compressing the original matrix ( a diaghunter parameter ) , sensitivity may be increased and computational time decreased ( as described below under diaghunter performance ) .
if this sort of compression is done , the original coordinates are recovered at the end .
as described earlier , the search order / scoring matrix is used in two ways : first , to specify the order in which the recursive search algorithm checks the hit matrix for the next diagonal element ; and second , to determine whether the overall diagonal score is sufficient to continue the current search .
this is particularly true during vertical or horizontal ( v / h ) gap extensions ( accomplished by any move that pushes the search in either a vertical - only or a horizontal - only direction ) .
the reason this kind of v / h gap extension is a special case is that in actual genomic similarity data , long runs of hits are much more common than would be expected in random data .
these occur because of gene families , common domains , or ( in nucleotide data ) high - copy repetitive sequences . at the same time , it is not uncommon for an insertion or a deletion in one genome to introduce a v / h gap in the hit matrix . therefore , it is essential to allow v / h extensions , but only after more preferable diagonal moves have been tried and exhausted . in figure 2 , this compromise is apparent as relatively small values in the positions representing vertical or horizontal moves .
however , tightly regulating near - vertical moves is less critical , because these kinds of relationships are not as common in genomic data .
the order of the algorithm , for a sparse hit matrix between two genomic regions of sizes m and n , with a compression factor of c , is o(mn / c ) . in practice , with a standard desktop computer , an appropriately compressed comparison of either mouse versus human or arabidopsis versus
processing times are not substantially longer for comparisons of the proteomes of the much larger mouse versus human genomes .
although m and n ( genome sizes measured in nucleotides ) are much larger in the mouse versus human case , c should also be proportionately larger because gene density is so much lower in mammalian genomes than in arabidopsis . in practice
, therefore , the order for proteome comparisons appears to depend approximately on the gene ( or other similarity ) counts in the two genomes rather than on nucleotide - count genome size .
the performance of diaghunter was tested with comparisons of predicted proteins in arabidopsis versus itself , and nucleotide versus nucleotide comparisons of arabidopsis versus itself and mouse versus human . in these tests , predictions were consistent with and were approximately as sensitive and selective as other published analyses of these datasets . in a comparison of arabidopsis chromosome 1 with itself ( biologically interesting because of extensive internal segmental duplication ) , diaghunter identified the same 24 duplication regions as reported by simillion et al . .
some of these regions are shown in the close - up of arabidopsis 1  1 diagonals in figure 1a , and all are shown in the thumbnail image of the whole - chromosome comparison in figure 3a ( the black call - out indicates the portion of the figure that is shown in detail in figure 1 ) .
results for the other arabidopsis chromosomes also closely match predictions by simillion et al . . a small modification of the hit matrix during data pre - processing ( using only the top 10 blast hits in addition to filtering by hit strength , and then lowering the acceptable blast hit - strength threshold in diaghunter ) appears to significantly improve diaghunter 's sensitivity and selectivity . for example , this results in the prediction of two additional probable synteny blocks in the chromosome 1  1 comparison ( data available at ) . simulation and sensitivity
tests in this paper , however , focus on the more difficult task of predicting synteny blocks in blast data not filtered by hit number .
it is interesting to contrast the peptide - based comparison in figure 3a with the nucleotide - based comparison in figure 3b .
the nucleotide - based comparison was generated with a blastn - based comparison of all 1-kb chunks of the nucleotide sequence of chromosome 1 pseudochromosome assembly against all others .
diaghunter predicts the large segmental duplications similarly in both datasets , but in the nucleotide comparison misses some of the smaller ones discovered by the more sensitive protein - protein comparison ( although a patternhunter   or blastz   dna - based homology search may provide greater dna - dna sensitivity than this rather crude block - based blastn approach ) .
likely reasons for the lower sensitivity in this nucleotide comparison are : the protein - based comparison uses strand - orientation information ( reducing the potential ' random background ' hits by half once any diagonal search is initiated ) ; the blastp similarity search is inherently more sensitive than blastn ; and the blastp hit matrix includes fewer blast hits that are due to repetitive dna .
in fact , the highly repetitive centromeric region produces such a dense feature in the nucleotide - nucleotide comparison that this region had to be masked and excluded from the search . in a comparison of mouse and human x chromosomes ( biologically interesting because of the high degree of homology that has been retained in this sex chromosome )
, the program found 15 - 18 extended diagonals , depending on search parameters ( 15 were found in the conservative search that produced figure 1b ) .
this is similar ( in number and , generally , in diagonal quality ) to the 16 synteny blocks identified by pevzner and tesler , although it is instructive to contrast the methods and results in more detail .
pevzner and tesler began with a set of " bidirectional best local similarities ( also called ' anchors ' ) " , generated by patternhunter .
this step is analogous to the blastp search conducted in the pre - processing step for diaghunter , although patternhunter aligns dna sequences rather than protein sequences ( as we used in the blastp search ) . because diaghunter relies only on a similarity matrix , suitably parsed output from patternhunter or other similarity - search methods
could also be used as diaghunter input - which would take better advantage of noncoding sequences and unannotated dna .
the next step in the pevzner and tesler study ( before inferring genome rearrangements , the paper 's primary objective ) was to construct synteny blocks based on these anchors .
this step , carried out by the grimm - synteny algorithm , connects anchor points ( similarity hits ) , if the distance between points is smaller than a given gap size , to form clusters of anchor points . '
small ' clusters are then deleted , leaving synteny blocks . in the comparison of human versus
mouse x chromosomes , with a gap threshold of 100 kb and patternhunter - generated anchor points , the grimm - synteny algorithm identifies 16 synteny blocks ( see figure 1b in ) .
this compares with 15 homology regions identified by diaghunter ( the search that produced figure 1 ) , using a matrix compression factor of 220 . at these thresholds , and using sparser protein - protein comparisons than were generated by grimm anchor points , the diaghunter algorithm misses two small diagonals identified by grimm , and makes one additional split of a diagonal .
these differences probably depend primarily on the patternhunter - blastp differences , although both algorithms are also sensitive to gap- or matrix - compression parameters .
the diaghunter search depends on several empirically determined parameters : the matrix compression , hit score cutoff , the average diagonal score , and the minimum hits to accept per diagonal .
these parameters may differ greatly from genome to genome , so for any new genome comparison some experimentation will be needed to find parameters that give a good trade - off between sensitivity and selectivity . in arabidopsis , for example , gene density is roughly one gene per 5 kb , but in the x chromosomes of mouse and human , the gene density is approximately one gene per 130 kb . for perspective , the entire arabidopsis genome , at roughly 125 mb , is smaller than either the mouse or human x chromosomes ( at roughly 150 mb ) , even though those chromosomes contain fewer than 1,100 predicted genes in ensembl .
the level of background noise is also much higher in the arabidopsis self - comparison , in which ongoing gene duplication , loss , transposition , and so on generate strong homologies unrelated to ancient segmental duplications .
this is evident in the many off - diagonal blast hits in the arabidopsis comparison in figures 1 and 3 .
the lower background noise in the mouse versus human comparison allows higher matrix compression levels , because random off - diagonal hits are unlikely to be brought close enough together to produce spurious predictions of collinearity .
a comparison of various parameters for the arabidopsis peptide self - comparison is shown in figures 4 and 5 .
figure 4 shows true and false positives in the chromosome 1  1 comparison under various matrix compression factors and diagonal ' quality ' thresholds .
generally , as matrix compression was increased over the range of 10 to 30 , the number of true positives increased , and the number of diagonal fragments decreased - corresponding to an increase in the ' coherence ' of the predicted diagonals .
in other words , as the hit matrix is more highly compressed , diagonal fragments are brought close enough together that they merge . beyond a certain point ,
diagonals that should be considered as separate might be artificially brought together , and hits that are not part of homology regions might be misjudged as members of diagonals .
the coordinates of nearby hits may also collapse to the same coordinate in the compressed matrix , resulting in loss of some information in the predicted diagonal pairs . in the parameter ranges used in these simulations ,
additional diagonals are not mispredicted in the chromosome 1  1 comparison , though interestingly , some false positives are seen at low compression factors as the program misidentifies diagonals in dense ' knots ' of local gene duplications .
therefore , there appear to be more disadvantages in this dataset from undercompression of the hit matrix than from what might be considered overcompression .
figure 4 also shows results for three different diagonal quality thresholds . the quality score is a running average of scores assigned from the hit score matrix depicted in figure 2
generally , a higher threshold produces more true - positive predictions at a given matrix compression factor .
figure 5 shows false - positive predictions in randomly distributed data that have the same density of ' background ' hits in arabidopsis  arabidopsis peptide comparisons , at the indicated blast bit score cutoffs and matrix compression factors . intuitively , if random data is brought close enough together
, then it will all merge so that essentially all hits will be falsely predicted as members of diagonals . in simulations ,
data densities were determined by observing the number of ' background ' hits in arabidopsis chromosome 1  2 at bit scores ranging from 400 to 650 ( in this dataset , these cutoffs correspond to expect values of approximately 10to 10 , respectively ) .
at each indicated compression factor and bit score cutoff ( grid intersections in the figure ) , diaghunter was run on 10 randomly distributed data sets at these densities .
each gradient represents the observed and extrapolated parameter combinations at which one additional false positive would be observed .
parameters for these data , therefore , should be chosen outside of the false - positive region . for a new genome comparison , tests with a range of compression factors fairly quickly show the point at which obviously spurious diagonals are predicted , and the sort of analysis presented here quickly guides the user to identify reasonable parameters . in figures 1 and 3 ,
the chosen parameters were compression factor = 26 and bit score cutoff = 650 , well outside of the false - positive region in these simulations .
it appears that better results can be obtained by additionally filtering to the top 5 - 20 blast hits , and lowering the bit score cutoff and matrix compression ( data not shown , but available at .
this has the effect of decreasing background ' noise ' due to high - copy sequences , while allowing the program to use more distant similarity relationships .
genopix2d is a general - purpose , cross - platform , flexible , queryable genomic dot - plotter / gene - family viewer , well suited to analyzing results of diaghunter or similar programs .
genopix2d is a desktop application implemented in tcl / tk , and should run on all platforms that support the tcl / tk interpreter .
genopix2d uses an interactive graphical user interface to display , query , filter , zoom , and plot 2d genome comparisons .
genopix2d takes as input simple , tab - delimited files containing blast hit information and gene coordinates .
results of a search ( for example , gene - family members , or diagonals detected by diaghunter ) can be painted in different colors defined by the user .
figure 6 displays the same region of the arabidopsis genome as in figure 1a , this time displayed by genopix2d .
members of three large gene families are shown : the nbs ( nucleotide - binding site)-containing resistance gene candidates , the cytochrome p450s , and the lrr ( leucine - rich repeat ) protein kinases .
interactive exploration of the region makes it possible to find all homologs to any selected dot ( blast hit ) on the image .
these features of genopix2d provide detailed analysis of syntenic regions detected by diaghunter at the single - gene level .
it is also worth noting that genopix2d can be used view comparative genomic data independently of diaghunter , requiring only the basic tcl / tk installation .
diaghunter is a cross - platform program that efficiently makes genome - scale comparisons and effectively predicts and reports large - scale homology regions .
its advantages include the ability to work with similarity ' hit ' matrices from essentially any source .
it is particularly tuned and suited for comparisons based on predicted proteins , for which strand orientations can be identified .
interactive visualization by genopix2d allows exploration of homology regions and of groups of related genes .
diaghunter is freely available at   and both diaghunter and genopix2d are available together at .
we thank andy baumgarten and georgiana may for helpful conversations during development . work on diaghunter
was supported by a usda national needs fellowship , a university of minnesota plant molecular genetics institute fellowship to s.c . , and nsf award dbi-0110206
( b ) a comparison of predicted genes in portions of the mouse and human x chromosomes ( mouse on the horizontal axis and human on the vertical axis ) .
note that the mouse / human window dimensions are approximately 12 times those shown in the arabidopsis comparison .
search order and scoring matrix for diaghunter . as the program walks through a matrix of similarity hits , each hit ( represented by a red x )
candidates for extension of the diagonal are picked first from those closest to the present hit , and closest to either a forward or reverse diagonal .
the search order and scores are represented by the area of the circles in the figure .
once either a forward or a reverse diagonal is initiated , only the reverse ( a )   or forward ( b )   version of the search order / score matrix is used for extension of the candidate diagonal , and the diagonal is recursively extended while candidate hits are available and the accumulated diagonal quality score remains above the quality threshold parameter . the sensitivity and selectivity of the search is increased if coding - strand information is included , as this reduces the number of ' random ' hits that might be considered at any step .
( b ) a comparison based on a similarity search between all 1 kb nucleotide segments from the tigr chromosome 1 assembly .
the region in the black rectangle in ( a ) is shown in figure 1 . in the protein - protein comparison ( a ) ,
hits with between genes with watson - watson or crick - crick ( ' forward diagonal ' ) orientations are shown in red , and hits between genes with watson - crick or crick - watson ( ' reverse diagonal ' ) orientations are shown in pink .
the use of strand orientation in the protein - protein comparison helps to explain the greater sensitivity of this search , compared with the nucleotide comparison in ( b ) .
the dense centromeric region encompassing the main diagonal in the nucleotide - nucleotide comparison was excluded from this search .
true - positive and false - positive diagonal predictions in arabidopsis chromosome 1  1 under various diaghunter search parameters .
true and false positives are judged relative to predictions reported in the literature . at low matrix compression factors ,
some diagonals are missed ( bold graph lines ) , and those that are identified are fragmentary ( thin solid graph line ) . at higher compression factors , random background hits should begin to ' merge ' to give false - positive predictions .
this has not occurred in these parameter ranges ( dotted graph lines ) , though the program did mistakenly predict short diagonals in dense clusters of locally duplicated genes at low compression factors , particularly at less stringent diagonal quality thresholds ( lines with asterisks ) .
parameters used in figures 1 and 3 are : quality = 9 , bit score = 650 ( approximately corresponding in this dataset to blast expect values of < 10 ) , compression factor = 26 .
abbreviations : q , diagonal quality ; sc , bit score ; cf , compression factor .
false - positive homology predictions in simulated data matrices with densities equivalent to those in ' background ' duplications in a blastp comparison of arabidopsis chromosomes 1 and 2 .
false positives increase rapidly if the matrix compression factor ( horizontal axis ) and hit density ( vertical axis ; determined by bit - score cutoff ) are such that simulated hits occur close enough together that spurious diagonals having the specified quality and hit number can be found in the simulated data .
parameters used in figures 1 and 3 are : quality = 9 , bit score = 650 ( approximately corresponding in this dataset to blast expect values of < 10 ) , compression factor = 26 . these selections are indicated with a star in this graph .
three large gene families , the nbs ( nucleotide - binding site)-containing resistance gene candidates , the cytochrome p450s , and the lrr ( leucine - rich repeat)-protein kinases   are highlighted in red , green and blue respectively .
blue crossed lines show an example of what is seen when a gene hit is selected : all homologs to those two genes are highlighted with vertical or horizontal yellow lines .
 the diaghunter and genopix2d applications work together to enable genomic comparisons and exploration at both genome - wide and single - gene scales . 
 diaghunter identifies homologous regions ( synteny blocks ) within or between genomes . 
 genopix2d allows interactive display of synteny blocks and other genomic features , as well as querying by annotation and by sequence similarity . 
Rationale
DiagHunter algorithm and implementation
DiagHunter performance
Features of GenoPix2D
Conclusions
Acknowledgements
Figures and Tables