Supplementary material to: i-ADHoRe 2.0: An improved tool to detect degenerated genomic homology using genomic profiles
Cedric Simillion, Koen Janssens, Lieven Sterck and Yves Van de PeerCorresponding author:
i-ADHoRe is a software tool that combines gene content and gene order information of homologous genomic segments into profiles to detect highly degenerated homology relations within and between genomes. The new version offers, besides a significant increase in performance, several optimizations to the algorithm, most importantly to the profile alignment routine. As a result, the annotations of multiple genomes, or parts thereof, can be fed simultaneously into the program, after which it will report all regions of homology, both within and between genomes.
Availability:The i-ADHoRe 2.0 package contains the C++ source code for the main program as well as various Perl scripts and a fully documented Perl API to facilitate post-processing. The software runs on any Linux or UNIX based platform. The package is freely available for academic users and can be downloaded from bioinformatics.psb.ugent.be
Simillion, C. , Janssens, K., Sterck, L. , Van de Peer, Y. (2007) i-ADHoRe 2.0: An improved tool to detect degenerated genomic homology using genomic profiles. Bioinformatics 24, 127-8.
In order to compare the performance of both alignment methods, i-ADHoRe was run twice on the same dataset, once using the original Needleman-Wunsch (NW) based alignment algorithm and once using the new Greedy-Graph (GG) based alignment method. The output alignments of both runs were compared to assess the difference of both alignment methods. Only pairs of multiplicons that are identical between both runs were considered. Because the detection of a higher-level multiplicon is directly dependant on the alignment of the profile used to detect it, most output multiplicons between both runs are slightly different from each other. Only those pairs of multiplicons were considered for comparison where the first and last genes of each segment were identical. Note that during the construction of profiles, the i-ADHore algorithm sometimes inverses part of a segment. Depending on the alignment method used, different breakpoints can be chosen for these inversions, which can lead to a different number of genes in alignments otherwise considered identical.
The quality of an alignment was assessed by counting the number of misaligned genes. A gene was considered to be misaligned if in a given profile a homolog was present on a different segment and this homolog was positioned in a different column than the reference gene. Conversely, a gene was considered aligned if a homolog was positioned in the same column in the alignment. The number of alignable genes is then the sum of both the number of misaligned and aligned genes. The lower the number of unaligned genes, the better the quality of an alignment is.
Table 1 shows the comparison of both alignment methods for the 21 pairs of identical alignments between both runs. In 11 cases the alignment created with the GG-method had a smaller fraction of unaligned genes whereas only in once case the NW-method gave a better result. For 9 cases no difference was observed, but for 6 of these this was because the number of unaligned genes was zero with both methods. This data shows cleary that the GG alignment method outperforms the original NW method.
Table 1: Comparison of the Needleman-Wunsch and Greed Graph based alignment methods.
VIB / UGent
Bioinformatics & Evolutionary Genomics
+32 (0) 9 33 13807 (phone)
+32 (0) 9 33 13809 (fax)