BACKGROUND
the nucleic acid research   <dig> database issue
<cit>  features  <dig>  databases covering various aspects of molecular biology including sequences, gene expression, structures, pathways and diseases.
most of these databases are independent of each other and have been created as a result of the respective developers’ domain of interest and resource limitations.
due to a lack of standard naming conventions, most of these databases prefer to assign their own custom generated identifiers  to the biological entities.
major public databases such as genbank
<cit>  and refseq
<cit>  use accession numbers, gene ontology
<cit>  uses a naming convention from organism specific databases, the hugo  gene nomenclature committee
<cit>  uses the gene symbol and a custom generated id, entrez
<cit>  uses numeric integers, sequencing projects use systematic names and biologists sometimes use additional aliases.
as an example, the breast cancer early onset gene has the official gene symbol of brca <dig> provided by hgnc and an associated id  <dig>  ensembl
<cit>  gene id ensg <dig>  omim
<cit>  id  <dig>  hpr  database
<cit>  id  <dig>  refseq id nm_ <dig>  genbank accession u <dig>  entrez gene id  <dig>  vega
<cit>  gene id otthumg <dig>  ucsc
<cit>  gene id uc001uub.
<dig>  uniprot
<cit>  id p <dig>  and gene aliases fad, fad <dig>  brcc <dig>  fancd <dig>  facd, fancd.
fortunately, there is a wealth of information available to the research community in a wide variety of databases.
however, it is often difficult to extract or integrate information about a particular biological entity from multiple resources.
for instance, a researcher may be interested in extracting functional information spread across different databases for a biological entity such as a gene or a protein; comparing two independent pathways which use different types of identifiers; or comparing results across species, platforms or labs.
the lack of a common identifier across these heterogeneous and sometimes redundant biological databases makes the functional analysis of biological data tedious, time consuming, and error prone.
one solution to handle heterogeneous databases is to use a global identifier for annotations such as the one described by miriam
<cit> .
miriam requires a global identifier to contain both the data source as well as an internal identifier.
for example, urn:miriam:hgnc:brca <dig> is composed of urn:miriam that defines the notation to be a urn  using the miriam scheme with data type hgnc and identifier brca <dig>  this method appears promising and has the potential to solve some of the previously mentioned problems, but very few databases follow this standard.
another solution is to manually search for these genes one by one in publicly available databases such as entrez, kegg
<cit> , or geo
<cit>  and infer their functionality.
this method is fruitful when the number of genes is small, but is impractical for high throughput experiments, where the number of gene fragments can be on the order of tens of thousands or more.
a third solution is to use an id converter tool that uses a database to store all possible annotations where a list of ids may be input as a query which is then converted into the corresponding target ids in a precise and efficient way.
one difficulty in the development and maintenance of such conversion tools is the varying granularity of the identifiers.
more specifically, the data generated by biological experiments may be at the locus, transcript, sequence or probe level, with varying coverage of a region of interest .
this granularity ranges from very fine, at the level of dna microarrays  through coarser granularity with sequence reads , transcripts , loci, and chromosomes.
it is also possible that annotations at the same level may have different granularities.
for example, among dna microarray probes, affymetrix®; probes are usually short  whereas agilent probes are longer  and cdna probes are generally ≥  <dig> nucleotides in length.
the relationships between entities at the same or different granularities may be either 1- <dig>  1-n, n- <dig> or n-m: for example, an affymetrix®; probe may span more than one est; more than one such probe may be contained inside an est; a cdna probe may contain zero, one or more affymetrix®; and agilent probes.
another difficulty in the development of such tools is the dynamic nature of annotations.
of late, rapid advances in sequencing and their declining costs have enabled researchers to perform novel sequencing as well as resequencing projects.
these result in an increased depth of coverage of a genomic sequence, with gaps being filled and repeats more accurately mapped.
sometimes, the sequence underlying a genetic entity may change, and on a less frequent basis the whole genomic sequence needs to be updated ,  <dig>  and  <dig>  respectively).
these changes may modify the structural and functional annotations of a genetic entity .
frequent updates in annotations also create problems in the manufacturing of dna microarrays.
microarray chips are designed and their probes are annotated using the current build of a specific genome.
regardless of the care taken in this design, the system will include flaws due to the combination of the delay inherent in the process of microarray design-manufacture-deployment  and the dynamic nature of annotations.
attempts to address these problems have been the focus of a number of previous studies.
gautlier et al.
<cit>  found redundancies in the annotations of affymetrix®; probes at a sequence level that map to multiple refseq genes.
such ambiguities may result in inaccurate interpretations.
affyprobeminer
<cit>  uses refseq and genbank’s validated complete coding sequences to regroup the probes on an affymetrix®; chip into consistent probe sets.
in their study, regrouping of the probes affected almost 65% of the probes on the hg-u133a chip.
harbig et al.
<cit>  reidentified the affymetrix®; u <dig> plus  <dig>  genechip®; array probes in an attempt to increase the reproducibility of microarray experiments.
they used blast
<cit>  to remap the probes against the genome and redefined approximately 37% of the probes.
these studies suggest that redefinition or reorganization of probesets will improve the analytical accuracy of the microarray data, a process that would be greatly facilitated by a means for high-throughput query and mapping/comparison of given sequences  to other genomic annotations stored across a wide variety of databases.
currently available id conversion tools
the problem of id conversion persists even though a number of tools exist to address this problem.
some of these are generic and perform id conversion for probes, genes, proteins, and additional annotations while others are more specific to dna microarray probes.
organism support varies with many of the tools catering to either a single organism or a small set of comparable species.
in addition, cross–species comparison is variable, with most methodologies providing only intra–species conversion.
almost every approach uses some sort of relational database with the unique identifier being ensembl ids, refseq ids, or custom generated ids.
a brief description of some popular tools follows.
david
<cit>  is a web based structural and functional annotation tool to extract biological meaning from a gene list.
it uniquely generates custom ids for querying a set of relations and is dependent on annotations from other databases.
a component of david, dict <cit>  , facilitates id conversion.
ease <cit> , developed by the david bioinformatics team, is a customizable, standalone, windows®; desktop software application, having similar analytic capabilities as that of david.
babelomics <cit>  is an integrated web based tool for structural and functional annotation with an id converter being one of its components.
this component uses a universal index linked to ensembl to create a database of  <dig> species.
g:convert <cit> , a component of g:profiler, allows arbitrary conversion of genes, proteins and probes into one another.
every alias in g:profiler is mapped through a three-level index of gene, transcript and protein ensembl ids.
for each index level, all corresponding ids are stored in the database.
the hyperlink management system and id converter system <cit>  automatically updates and maintains hyperlink information among major public biological and chemical databases.
it downloads data everyday from authoritative databases and produces a large correspondence table which is used to show the most up-to-date url for genes of interest.
users can use cgi programs to create hyperlinks to this data.
synergizer <cit>  assigns a unique internally generated identifier, “peg”, to all external ids that refer to the same biological entity.
it mostly uses the ncbi “gene2accession” file to maintain a database of synonym relationships and produce a simple web interface.
madgene <cit>  uses correspondence tables and allows conversions in an efficient way.
the clone/gene id converter <cit> , matchminer <cit> , the gene name converter in genemerge <cit> , resourcerer <cit>  and genelynx <cit>  are additional id conversion tools.
some of the id conversion tools are more specific, such as those that work only at the probe level.
gatexplorer <cit>  is a web based tool for analysis and visualization of affymetrix®; probes at the genomic and transcriptomic level.
it performs de–novo mapping of all the probes of affymetrix®;’s expression and exon arrays against the transcriptome of the corresponding organism using blast and records the coordinates on the genome.
unmapped probes are mapped to an ncrna database downloaded from rnadb.
only the perfect match alignment is selected while mapping these probes.
the location of a gene or probe on the genome can be visualized along with all the transcripts present in that region.
netaffx™ <cit> , provided by affymetrix®;, performs id conversion of affymetrix®; probes for different organisms and has a feature to perform structural and functional annotation.
plandbaffy <cit>  is a probe-level annotation database for affymetrix®; microarrays  that uses blat
<cit>  to map individual probes onto the human genome.
these probes are then annotated using information extracted from refseq.
probematchdb <cit>  uses a number of public databases to perform cross-species and cross-platform probe mapping.
the database conversions are enabled by unigene and homologene identifiers.
uniprot’s
<cit> id mapping tool works on the gene and protein level and converts gene ids into uniprot ids and vice versa.
some software tools have unique methods for mapping between different ids.
onto–translate <cit>  converts one type of ids into another by calculating the optimal path between ids, taking into account the “trustworthiness” of data contained in various databases.
the aliasserver <cit>  uses a custom generated unique 64-bit reference identifier which is computed from the amino acid sequence using the crc  algorithm where each id is a unique combination of species identifier, type of database and the id itself.
some databases/tools aid in id conversion but do not function as a full fledged id conversion tool.
biomart <cit> , earlier known as ensmart <cit> , provides a web and api interface to download data such as go terms, genes, transcripts and expression arrays from different databases using filters.
bridgedb <cit>  provides an interface to connect bioinformatics tools such as cytoscape, pathvisio, or wikipathways with other mapping services such as ensembl, picr
<cit> , and any local database or text files.
it is intended to be used by bioinformatics developers and works on the novel idea of mapping custom identifiers to established identifiers such as ensembl id and then relies on ensembl to provide the rest of the conversion.
side by side feature comparisons of these tools are provided in table
<dig>  data sources for select tools are listed in table
<dig>
aabbreviations: annot.
view: custom annotation view, annot.
: annotation , org.
: organisms , prots: proteins, affy: affymetrix®;, trans: transcripts, seqs: sequences, ens.
: ensembl, corr: correspondence, acc: accession, bio: biological, na: not applicable, cnd: could not determine, ⇓:download knowledgebase, vm: virtual machine.
drawbacks associated with existing approaches
most of the id conversion tools mentioned above use a two step conversion method.
to convert an id “a” to id “b”, the first step is to use a correspondence annotation relation or table to find a common intermediary id “c” .
this common id “c” is then converted into target id “b” using another correspondence table.
some tools use ensembl or refseq as an intermediary while others generate unique custom identifiers.
for example, the clone/gene id converter and gatexplorer use ensembl id, plandbaffy uses refseq whereas david and synergizer use a custom generated david id and peg respectively.
these tools convert smaller fragments  into coarser genetic entities  using inferred annotation level information irrespective of the fact that these small fragments may not be representative of the annotation as a whole.
these methodologies also tend to lose structural and other information available at the probe or sequence level.
as stated previously, annotations are dynamic and databases such as ensembl and refseq are updated daily making it difficult to keep the databases of id conversion tools current.
this is more problematic when the intermediate ids are custom generated as these require more effort to update.
most of the tools are based on a relational database and the dynamic nature of annotations may introduce database anomalies because of the frequent insertion, deletion and updating of the annotations.
if a gene is discovered, deleted or updated in any of these databases, or the annotations corresponding to an entity are added, deleted or updated, then all the databases or correspondence tables also need to be updated.
in the case of microarray experiments, if a probe corresponds to a recently deleted entity then that probe annotation needs to be edited as well.
updating any of these authoritative databases may induce a chain-reaction for any other systems using that information and any experimental result deduced from the updated probe may become invalid.
those tools that generate their own unique identifier such as david, synergizer or babelomics, although efficient, face a similar situation and need to be updated frequently.
as updating an annotation database is labor and resource intensive, some of the tools cannot afford to update their knowledgebase regularly.
absolute  method for id conversion
a feature of biological entities that is currently ignored in id conversion is the sequence mapping information.
for species where a reference genome is available, all nucleic acid and protein-based annotations, no matter the granularity, can be aligned to that reference genome sequence and therefore annotated by genomic intervals.
once the absolute genomic coordinates on a reference genome for all entities have been determined, these can be queried to find all overlapping entities, thus performing id conversion.
this conversion uses the same two step method as adopted by most of the id conversion tools, considering the genomic coordinates as the basis of conversion, rather than the annotation level information used by other tools.
compared to other types of intermediate ids, the intervals on a reference genome sequence are relatively static, and remapping of entities to modified genomic sequences is relatively trivial, making it possible to easily update the system.
using interval trees, conversion by finding overlapping intervals is fast and efficient
<cit> .
figure
<dig> shows the steps to perform sequence-based or absolute id conversion.
in the figure, all transcripts corresponding to probe a are being found.
the first step in this conversion is to find the genomic coordinates corresponding to probe a and the second step is to find all transcripts that span those coordinates.
in this example transcript  <dig> and transcript  <dig> are the converted ids corresponding to the probe a. transcript  <dig> is not represented by probe a as the underlying genomic sequence is not part of transcript  <dig>  subsequent sections describe the design and implementation of a genomic interval based id conversion tool, absidconvert.
methods
the design of absidconvert was accomplished using a preprocessing and a query step.
in the preprocessing step, reference genomes were downloaded from the ucsc genome browser  and the ncbi website.
the sequence information for a variety of identifiers at different granularities such as probes, sequences , transcripts and genes were downloaded from their respective authoritative websites or ucsc.
the identifier types include affymetrix®; probes, agilent probes, est sequences, ensembl transcripts and entrez genes.
each identifier sequence was mapped to the respective genome using either blat
<cit>  or bowtie
<cit> .
blat was used to map longer  sequences, while bowtie was used for relatively short  sequences such as affymetrix®; and agilent probes.
each identifier was then annotated with structural information such as start , end , size  and chrom .
this information was collected for each identifier as a genomic interval.
genetic entities with multiple exons such as transcripts were treated differently as there are two ways in which these can be structurally annotated.
one method is to use the extreme ends  as their intervals including both the exons as well as intronic regions, or alternatively exclude the intronic regions and assume the transcript’s genomic intervals are an assembly of genomic intervals of the participating exons .
finally organism and identifier type specific interval trees were constructed and stored.
a list of all identifiers and their type was also stored in a relational database to facilitate batch look-up for the types of identifiers.
figure
<dig> shows the design steps of absidconvert.
once structural annotation for each of the identifiers is available, absidconvert can query this information.
this query step uses the structural annotation information of each identifier and the organism specific database generated from the previous step.
absidconvert assumes two biological entities  are the same if their genomic sequences are also the same, overlap or one is contained within the other.
as the number of annotations are large and frequent insertions and deletions are routine, an efficient data structure for storage and computational operations is needed.
considering that the structural annotation is in the form of genomic intervals, a modified red-black tree, known as an interval tree, is used to store the information for all ids.
an interval tree maintains a dynamic set of elements, with each element x containing an interval int.
this int stores the start and end of the interval apart from other auxiliary information.
this data structure is dynamic in nature and can perform insertions and deletions efficiently in time o, where n is the number of elements.
interval trees have been shown to be efficient for working with a large number of genomic intervals
<cit> .
there are four possible ways in which absidconvert may be queried:
• lookup identifiers: given a mixed list of identifiers, absidconvert can determine the types of identifiers in the list.
this step uses the relational database created in the preprocessing step and can efficiently categorize the ids in the list.
• batch conversion of ids: given a list of identifiers, absidconvert uses the interval tree to find their genomic coordinates.
once the coordinate information is available, all overlapping identifiers can be found by querying the interval tree.
this uses the iranges
<cit>  and genomicranges
<cit>  packages internally to maintain the genomic intervals which are based on allen’s interval algebra
<cit> .
users can specify various range parameters using the interface.
the overlap type  parameter may take any one of ‘any’, ‘start’, ‘end’, ‘equal’ or ‘within’ as its value.
by default ‘any’ overlap is accepted.
if ‘type’ value is ‘start’ or ‘end’ then the query intervals are required to have matching ‘start’ and ‘end’ respectively with subject intervals in the database.
if ‘type’ is ‘equal’ then only those subjects are retrieved which have the exact same coordinates.
for ‘within’, the query must be contained wholly within the subject intervals.
another parameter is for specifying the maximum gap  between subject and query intervals to consider them as overlapping.
the default value is zero which assumes there should not be any gap between the subject and query intervals.
this parameter is useful for finding genes in the flanking regions of the specified intervals.
the third parameter is the minimum overlap  size that specifies the minimum number of overlapping base pairs needed to consider the query and subject an overlap.
the default overlap value is one.
the last parameter is the ‘select’ parameter that specifies which type of overlaps will be reported.
by default, all overlapping intervals will be reported.
selecting ‘first’, ‘last’ and ‘arbitrary’ will report first, last and arbitrary overlapping intervals from the result.
a simple example using intervals is shown in figure
<dig>  in this case, the reference genome is  <dig> bp long.
the subject database contain four intervals s <dig>  s <dig>  s <dig> and s <dig> that represent the interval database.
query intervals also consist of four intervals q <dig>  q <dig>  q <dig> qnd q <dig>  considering default values for range parameters, q <dig> overlaps with s <dig>  q <dig> and q <dig> overlap with all the intervals in the subject, whereas q <dig> overlaps with s <dig>  s <dig> and s <dig>  if the values of the parameters are type=‘within’, maxgap =  <dig>  minoverlap= <dig>  select= ‘all’ then q <dig> overlaps with s <dig>  q <dig> with s <dig> and q <dig> with s <dig> and s <dig>  if the values of the parameters are type=‘end’, maxgap =  <dig>  minoverlap =  <dig>  select= ‘all’ then q <dig> overlaps with s <dig>  q <dig> with s <dig> and q <dig>  and q <dig> with s <dig>
• intervals as input to absidconvert: a unique feature of the id conversion is to find target identifiers corresponding to a given interval.
for example, next-generation sequencers generally map the dna sequences or reads to a reference genome and output the intervals for each aligned reads.
finding desired target identifiers corresponding to these intervals is routinely required.
absidconvert efficiently converts these coordinates into target identifiers in a high throughput manner.
for instance, a user of absidconvert is able to take a set of intervals upstream of a set of transcription start sites to determine if any features are annotated proximal to the regions of interest.
• sequences as input to absidconvert: sometimes a user may be interested in finding all identifiers that correspond to a particular sequence or a list of sequences.
for instance, a user may be interested in finding all gene names and entrez ids corresponding to a set of sequences.
in this case, absidconvert maps these sequences to the corresponding genome  and determines the genomic intervals they belong to and then retrieves all the desired target identifiers that overlap these intervals.
due to the computational complexity involved in mapping long sequences using a generic mapping algorithm such as blat or blast, the web version of absidconvert supports only short sequence mapping using bowtie.
longer sequences can be mapped using blat in the virtual machine version of absidconvert.
sequence output from next-generation sequencing technologies can be catered efficiently using absidconvert.
alternatively, the coordinate information may be obtained by submitting the sequences to galaxy
<cit>  or the ucsc genome browser and subsequently inputting the intervals using absidconvert.
mapping parameters can be specified by the user through the interface.
parameters include the maximum number of mismatches which can range from zero  to three.
the second mapping parameter specifies which type of alignments are to be reported.
the default value is ‘all best’ in which all best alignments will be reported by bowtie.
however, ‘all’, ‘k’ or ‘k best’ can be selected for bowtie output.
absidconvert also has another parameter ‘do not report ’ that takes a positive integer value which specifies that bowtie will suppress all alignments for a particular read if the total number of reportable alignments for that read is more than the specified value.
the default value of - <dig> specifies that all alignments will be accepted.
for instance, if this value is set to  <dig>  then bowtie will suppress all those alignments for reads that map to  <dig> or more locations on the genome.
this is an effective option to mask repeat sequences or small sequences from appearing into the output because their probability to map at multiple locations on the genome is higher.
absidconvert supports  <dig> major species for performing id conversion on a list of identifiers and a list of intervals.
it also has sequence level mapping support for  <dig> major species including homo sapiens, mus musculus, rattus norvegicus, bos taurus, gallus gallus, sus scrofa, xenopus tropicalis, anopheles gambiae, drosophila melanogaster, caenorhabditis elegans, saccharomyces cerevisiae, and danio rerio.
absidconvert converts the input  into target identifiers with links to authoritative databases.
all intermediate interval files are available to download for later use.
it also generates custom annotation files that can be used to view the ids simultaneously  as a custom track in the ucsc genome browser.
the performance and potential uses for absidconvert are discussed in the following sections.
RESULTS
intervals vs. relational database
the genomic coordinate information for different identifier types mapped to  <dig> species were stored as intervals.
an interval tree method was implemented and used to store and query the corresponding interval information for each identifier type.
for comparison with relational databases, an equivalent mysql database was implemented to perform id conversion based on coordinate information, and the run time for both of these methods were compared.
run–time comparisons of the interval tree and mysql implementations were performed using randomly sampled rat est ids which were subsequently converted to entrez gene ids.
to test the actual runtime, the number of est ids was increased exponentially for each test point and the corresponding execution time  was measured.
the run time complexity of the interval tree maintained a constant rate while the relational methodology grows in linear fashion, allowing for the conversion of millions of identifiers in only a few seconds .
further analysis of conversion runtime was performed using  <dig>  random sampled ids from affymetrix®; rat230_ <dig> microarray probes, agilent cgh105a microarray probes, refseq ids, ensembl transcripts, entrez genes, hugo gene symbols and est ids which were converted into one another using the web version of absidconvert .
the extreme left column represents the source identifiers which are converted to target identifiers shown in first row.
the numbers in small parentheses in the first row show the total number of genomic coordinates for individual id types .
since absidconvert supports conversion to multiple target types, the last column represents the time elapsed when an input type is converted into all other id types.
run–time comparison
direct comparison to other id conversion approaches is not straightforward due to the differences in annotation information , supported id types, and development/deployment platforms.
in order to test the runtime of comparable solutions , a varying number  of affymetrix®; rat230_ <dig>  microarray probesets were converted to entrez ids .
when the number of probe sets converted was small , the conversion time for all tools was nominal.
for a moderate number of probe sets  madgene, david and absidconvert performed similarly , while gatexplorer took around a minute and clone/gene id converter took  <dig> minutes ).
as the number of probe sets further increased, all of the tools, with the exception of madgene and absidconvert, were incapable of tractably handling such a large number of inputs.
since the affymetrix®; rat230_ <dig>  has roughly  <dig>  unique probe sets and over  <dig>  individual perfect match probes, a run time comparison for a large number of inputs  was performed by converting randomly sampled human transcripts into entrez ids .
for  <dig>  inputs, only madgene and absidconvert completed successfully, taking  <dig> sec and  <dig> sec, respectively ).
the run–time complexity for absidconvert compares favorably to other similar tools, demonstrating its applicability in the analysis of high throughput data.
output accuracy
the accuracy of conversions performed using absidconvert was assessed based on the overlap of the successfully converted ids with those found using other tools for three types of conversions.
in the first conversion,  <dig>  unique entrez ids were randomly sampled from the “org.hs.eg.db” bioconductor annotation package and converted to their corresponding official gene symbols.
ten id conversion tools, from a total of  <dig> tools listed in table
<dig>  can perform this conversion.
considering ncbi as the authority for entrez ids, the accuracy of different conversion tools were evaluated using the following assumptions:
<dig>  ncbi contains the most up to date information and its annotations are correct.
<dig>  an entrez id may be annotated by more than one gene symbol.
<dig>  given an entrez id x, if a tool converts x to a set of gene symbols, y , and ncbi annotates x to another set of gene symbols, z , then accuracy terms can be defined as:
• true positives  are those conversions in which the converted gene symbol set contains all the gene symbol annotated by ncbi .
• false positives  are unexpected results.
this includes incorrect conversions , as well as those conversions in which ncbi does not annotate an entrez id with any gene symbol, but a tool finds some gene symbol corresponding to that entrez id .
• false negatives  are missing conversions in which a tool could not find corresponding gene symbol .
• true negatives  are the correct absence of conversion in which ncbi as well as a particular tool does not convert an entrez to any gene symbol .
<dig>  accuracy is defined as
%accuracy=tp+tntp+tn+fp+fn× <dig>
table
<dig> shows the contingency table and associated statistics for the conversion of  <dig>  entrez ids to gene symbols.
absidconvert converted a total of  <dig> entrez ids with an accuracy of  <dig> % followed by david , madgene  and hms & ic .
although onto-translate converted a total of  <dig> entrez ids, it has more fp conversions than hms & ic and therefore a lower accuracy.
we further investigated the conversions from the top four tools on the basis of their accuracy and summarized the results in a venn diagram ).
absidconvert converted a total of  <dig> entrez ids which are missed by the other tools.
ncbi places all these entrez ids onto the reference genome and annotates them with gene symbols that are in agreement with absidconvert .
of these  <dig> entrez ids,  <dig> are categorized as “pseudo”,  <dig> as “miscrna”, four as “protein-coding”, three as “unknown” and one as “other”.
absidconvert was unable to convert a total of  <dig> entrez ids, out of which  <dig> ids were not converted by any of the tools examined.
of the  <dig> entrez ids that absidconvert was not able to convert but other tools were , most were either “not on current assembly”, meaning that the reference sequence for that entrez id could not be mapped to the current genome , but could be mapped to previous genome assemblies; or “not annotated on reference assembly”, indicating that the sequence cannot be found on the reference assembly at all .
five conversions were found where the entrez ids reported had since been deleted and replaced .
in a second conversion test,  <dig>  randomly sampled entrez ids were converted to refseq ids using ten of the  <dig> tools listed in table
<dig> .
there are many different classes of refseq ids, including mrna , rna , protein , as well as predicted versions of each one .
how refseq ids are segregated for conversion differs among the tools tested.
for example, a number of tools combine all the different types of refseq ids into one converted id type while others treat each one separately.
other tools ignore the predicted refseq ids and only consider mrna and rna.
for example, absidconvert’s refseq database combines both mrna and rna, whereas madgene includes predicted products .
david and synergizer have separate options for rna and mrna refseq.
therefore, to enable comparison between all the tools, only those conversions that result in mrna or rna refseq ids are considered, and for those tools that report them separately, the results from both conversions were combined.
in addition, any predicted refseq ids  were removed.
using the same assumptions as reported for the entrez to symbol conversion, the accuracy of conversion for each tool was calculated .
of the  <dig>  entrez ids used, ncbi annotates only  <dig> with one or more refseq.
in this case, the accuracy for the various tools ranged from a high of  <dig> %  to a low of  <dig> % .
the results from the four most accurate tools were investigated further.
<dig> entrez ids were converted commonly by all tools ).
absidconvert converted  <dig>  followed by madgene , david  and onto-translate .
five conversions specific to madgene were not found by absidconvert .
in this case, absidconvert correctly mapped the entrez ids to the genome ; however, the corresponding refseq ids were not in the data obtained from ucsc.
other conversions that absidconvert did not report were found to be false positives reported by other tools.
for example, david and onto-translate both reported converting “4586” to “nm_017511” and “441956” to “nm_001013729”; however, the genomic intervals for those ids do not overlap, and both refseq ids are shown in ncbi as “permanently suppressed”.
for the twenty conversions specific to david, the reported refseq ids were found to be associated with different entrez ids in ncbi .
the thirty-eight entrez ids converted only by absidconvert were investigated further to verify whether they were “correct”.
thirty-three are in agreement with the ncbi data .
for the other five, we examined the genomic intervals of both the entrez ids and reported refseq ids to verify that they do indeed overlap .
in all cases the converted ids do have overlapping intervals with two of the entrez ids discontinued and replaced since the initial construction of the absidconvert database, “100505905”  and “100652874” .
to better assess the accuracy of absidconvert compared to other tools, the entrez to refseq id conversion was repeated ten times, randomly choosing  <dig>  entrez ids each time.
out of the  <dig>  randomly selected entrez ids,  <dig>  were unique.
absidconvert converted  <dig>  , followed by madgene , david  and onto-translate  ).
a total of  <dig>  of the ids were exclusively converted by absidconvert.
in the third conversion,  <dig>  randomly sampled human affymetrix®; genechip hg-u <dig> plus  <dig>  probesets were converted to agilent cgh44b probes ).
this type of cross-platform conversion is important in meta-analysis studies where results are drawn by integrating and analyzing data from a number of independent studies/platforms.
as this type of conversion is available only in synergizer, we compared the conversion results of this tool with absidconvert.
synergizer converted  <dig> whereas absidconvert converted  <dig> probesets.
the reason for the small number of conversions is primarily due to the design differences of the probes on these chips.
two questions required deeper investigation:  <dig>  why was absidconvert not able to convert  <dig> affymetrix®; ids that were successfully converted by synergizer; and  <dig>  are the  <dig> conversions exclusive to absidconvert valid?
to answer these, we extracted the design annotation of all the affymetrix®; genechip hg-u <dig> plus  <dig>  probesets provided by affymetrix’s netaffx
<cit>  along with the design annotations for the agilent cgh44b probes supplied by agilent
<cit> .
these provided the individual locations of each probe on the hg <dig> genome, thereby enabling investigation of the interval separation between the probesets.
in order to examine the  <dig> probesets converted by synergizer but not by absidconvert, the genomic location of the affymetrix®; probesets were compared to the genomic locations of the agilent probes.
fifty-six  of the probes are separated according to their genomic locations and do not overlap at all.
this separation ranges from  <dig> to  <dig>  bp with a median separation of  <dig>  bases.
further analysis determines that these all lie in the regions between the individual probes of the respective probesets and therefore have no shared sequence identity.
most of the id converter tools including synergizer map the genetic entities  spanning tens of bases to an intermediary such as ensembl that is at a coarser granularity spanning a few kilobases with possible intronic regions.
while performing conversions, these tools only use the probe annotation, disregarding the actual sequence information.
the above false positives provided by synergizer are likely the result of ignoring the sequence level information as the two types of probes actually span different genomic intervals.
next we considered conversions found exclusively by absidconvert.
based on the official annotation from netaffx™, we found that intervals for all  <dig> affymetrix®; probesets actually contain or overlap the converted agilent probes with a mean overlap of  <dig>  bases.
considering that most of the agilent probes are  <dig> bases long and an affymetrix®; probeset contains overlapping  <dig> bp probes, this indicates most of these agilent probes are contained in the affymetrix®; probeset region.
these probesets were checked at the probe level and it was determined that these converted agilent probes overlap with individual affymetrix®; probes to some extent, or are completely contained with a mean overlap length of  <dig>  bp.
we are not sure why synergizer was unable to convert these  <dig> probes; however, the official annotation confirms these annotations and bolsters our confidence in the power and accuracy of our sequence based id conversion.
case studies
three illustrative case studies were explored to demonstrate the capabilities of absidconvert.
the first case study considers sequence-based mapping of identifiers in a comparative genomics analysis of organisms involved in malaria; the second examines remapping of probes to annotations within and across species using a historical cdna platform from incyte; and the third identifies ensembl transcripts mapped by agilent and affymetrix®; arrays.
case study 1: comparative genomics: plasmodium mapped to human and anopheles gambiae
recent studies have surveyed the role of both host and pathogen genetic variability to determine molecular signatures for host-pathogen interactions
<cit> .
while the interactions between a pathogen and its host are often mediated by the host immune system responses to the pathogen, host-pathogen relationships theoretically have the potential to create a metagenomic environment whereby the total transcriptome is contributed by both the host and pathogen genes.
in some cases, such as neisseria meningitidis, a direct interaction between host and pathogen genes has been demonstrated
<cit> .
as an illustrative example, it might be possible that shared sequence similarities between pathogen and host genes play a role in host gene regulation via pathogen genes and gene products that provide additional promoter sites, mirna targets, and binding motifs similar to those found in the host.
to test the feasibility of this possibility in the context of malaria, we used absidconvert to identify coding sequences identical between the plasmodium falciparum  and plasmodium vivax  species and the human and anopheles genomes.
plasmodium is a parasite responsible for causing malaria in humans primarily in tropical and sub–tropical areas.
about  <dig>  billion people are at risk of this disease, leading to  <dig> million malaria cases and one million deaths worldwide every year .
altogether four plasmodium species are responsible which are carried by the female anopheles gambiae mosquito.
pf and pv are the most common, with pf being the deadliest.
coding sequences for each gene for these two species were downloaded from the plasmodb website
<cit> .
the total number of coding sequences in pf and pv were  <dig>  and  <dig>  respectively.
sequences for each of these genes were then fragmented into  <dig> base-pair  long sequences with an overlap of  <dig> bp.
the fragmented sequences were given a unique name by attaching a numerical suffix onto the gene name that denotes the order of appearance in the gene sequence.
these fragmented sequences were analyzed using absidconvert by selecting default parameters including no mismatch while aligning to the anopheles gambiae  and homo sapiens  genomes .
a total of  <dig> gene fragments from pf ) had an exact sequence match to  <dig> human genes ).
for pv, the aligned number of gene fragments and corresponding genes were  <dig> ) and  <dig> ), respectively.
these numbers indicate that the gene fragments align to multiple locations on the human genome.
among genes that were mapped from pf and pv gene fragments, a total of  <dig> genes were common.
when the same gene fragment sequences from pf and pv were aligned to the anopheles gambiae genome , a total of  <dig> ) gene fragments from pf were mapped to  <dig> ) different genes, showing that the correspondence between the gene fragments and genes is largely one–to–one.
these numbers for pv were  <dig> ) and  <dig> ), respectively.
a more detailed analysis of the genes identified using ontological information indicates a significant enrichment in cell adhesion processes .
these are present in the go terms ‘cell-cell adhesion’ , but also implied by the large number of terms regarding neuronal axonogenesis and synapse formation, which require specific regulation of cellular adhesion.
while purely speculative at this point, it is possible these plasmodium genes interact with the human host to help sequester human erythrocytes in small blood vessels which aids in the invasion plasmodium into the immune system
<cit> .
while benchtop analysis of these genes is needed to determine if the “feasible” actually occurs, it is clear that analysis using absidconvert has identified, via cross-species analysis, a limited set of genes that can be further interrogated for understanding the malaria-related pathophysiology, including the process of plasmodium incorporation into erythrocytes.
case study 2: reinterpretation of prior datasets
annotations used for dna microarray studies quickly become out–of–date as more knowledge emerges about a species’ transcriptome.
in addition, there are instances where one microarray platform may be used to measure gene products from a comparative species.
for example, incyte arrays spotted with human ests have been used to query gene expression levels in mouse and/or rat, based on the assumption that the human ests would bind to and provide measurements of the corresponding gene in rodents
<cit> .
using the original est sequences spotted on the array from these studies, we sought to verify the current annotations of the ests, and also determine which rodent genes should bind the ests based on sequence alignment to the human, mouse, and rat genomes.
original est sequences were found by searching two sources using the incyte ids supplied on the chip.
the first source was the ncbi est database, using a search string composed of “image:” and the incyte clone id number .
the second source was the open biosystems database , using a search string composed of “lifeseq” and the clone id number.
in some instances, multiple est sequences were returned for each clone id.
a total of  <dig>  sequences were downloaded and aligned to the genomes of human, rat, and mouse using absidconvert with the default blat settings.
the genome wide best alignment was found for each probe by considering only those alignments falling within 5% of the maximal alignment score ).
corresponding to each of these aligned coordinates, overlapping entrez ids were found for all three organisms.
out of the  <dig>  human incyte ids which had corresponding genomic interval,  <dig>  have at least one human entrez id associated with them.
this number was  <dig>   for mouse and  <dig>   for rat ).
homologous genes can be compared across species using ncbi’s homologene resource
<cit>  when gene names are known.
however, if sequence information is available, it would be best to use that sequence information to determine if homology exists based on sequence conservation, particularly in cases where probes of known sequence are being used to measure a specific gene, such as in dna microarrays or in–situ hybridization.
both methodologies were applied to the incyte array used in
<cit> .
for the homologene based comparison, all of the incyte ids that map to at least one entrez id using absidconvert were used to determine if a homologous gene exists, and if so, if there are corresponding entries for each of the species studied.
similarly, for those incyte probes matching at least one entrez id, the sequence was used as a query into each of the other species using absidconvert to determine if the probe maps to and overlaps an entrez id in a cross-species sense.
as table
<dig> indicates, using the homologene conversion alone yields a high number of homologs ; however, using the sequence level information, it can be seen that a much lower percentage of probes  actually map to known entrez gene regions in the other species.
these demonstrate that only a small number of the probes on the array should be utilized for cross species comparisons.
amapped†:number of probes mapped to genome; entrez‡:mapped probes with entrez id; homolÂ§: probes with entrez id as well as homologene id; hom: homologene based homologs; seq: sequence based homologs determined using absidconvert.
case study 3: meta–analytic studies across platforms
meta-analysis enables the integration of many different experiments with a common research hypothesis.
however, high-throughput -omics meta-analyses are hindered due to the heterogeneity of dna microarray array designs , data acquisition, analysis, and inter- and intra-study variability.
therefore, many meta-analyses use the same species or even the same array platform to mitigate some of these heterogeneities.
however, many studies do still attempt to perform cross-platform and inter-species meta-analyses, and tools such as ailun
<cit> , a-madman
<cit> , and lola
<cit>  enable cross-species meta-analysis using entrez id, gene symbol or other ids as a conversion intermediary.
absidconvert can perform cross-platform/-species analysis efficiently using the sequence based approach.
we previously demonstrated that absidconvert efficiently and accurately converted affymetrix®; hg_u133plus <dig>  probes into agilent cgh105a probes, among other types of conversions.
to determine how comparable two microarray studies using different array platforms on a common organism could be, affymetrix®; hg_u133plus <dig>  and agilent cgh105a probe sequences were mapped and converted to corresponding human ensembl transcripts using the default absidconvert parameters.
for the affymetrix platform,  <dig>  out of  <dig>  probes were mapped to one or more transcripts, with  <dig>  of the total ensembl transcripts  being mapped .
this leaves  <dig>  ensembl transcripts that were not mapped by any affymetrix®; probes.
for agilent,  <dig>   mapped to  <dig>  ensembl transcripts.
<dig>   ensembl transcripts do not have any mapped agilent cgh105a probes.
the number of shared ensembl transcripts between platforms was surprisingly small , indicating that each platform appears to have probe specific subsets of ensembl transcripts.
the number of ensembl transcripts not probed by either platform was surprisingly large.
this appears to be due to a lack of probes designed to bind those ensembl transcripts, as the majority of unmapped transcripts are much shorter than those that are mapped .
as figure
<dig> illustrates,  <dig>  transcripts should be directly comparable between affymetrix®; hg_u133plus <dig>  and agilent cgh105a, while a large number of transcripts are not available in one or the other  platforms.
CONCLUSIONS
absidconvert is the only known gene id conversion tool based on genomic coordinates/intervals of which we are aware.
this is a novel and important contribution in the realm of gene id conversion due to the large variety of genetic entities in current use by biologists, the need to convert between them, and the fact that most biological entities  have an associated sequence.
mapping of the entity sequence to a reference genome sequence provides the concomitant genomic interval that allows determination of other entities that have overlapping genomic intervals.
the interval basis of absidconvert provides ease of flexibility with respect to any additions, deletions or updates of the underlying objects, requiring only adding of intervals, removing intervals, or modifying the intervals themselves, respectively.
this makes it possible to easily keep the structure updated as the current state of biological knowledge changes.
a major update is only required when the underlying genome changes, a fairly rare occurrence for most organisms, especially when compared to how often other genomic databases are modified.
these intervals also allow easy discovery of genetic entities that only partially overlap with queried ids/intervals, or that are within a specified distance nearby.
more frequently, researchers are interested in those genes that are near specific genomic intervals corresponding to various types of genetic control elements such as transcription factor binding sites, enhancers, untranslated regions, and hyper/hypo methylated regions.
absidconvert makes it easy to find those entities that overlap or lie nearby regions of interest.
with the incorporation of a sequence mapping algorithm, absidconvert integrates the determination of genomic intervals for any supplied sequence, making it possible to easily find and convert between ids from any platform and organism, such as the examination of correspondence of the human est clones with rat and mouse genes  and of plasmodium and human genes .
we do not know of any other system that can easily accomplish these types of analyses.
absidconvert can greatly facilitate the work of those who are involved in meta analyses studies.
when comparing studies where either the species and / or platform varies, this methodology will have clear advantages over others as it is based on common genomic coordinates.
the use of an interval tree structure makes it possible to perform large conversions quickly and efficiently.
this method is efficient while dealing with genomic intervals and has a significant advantage over other methods such as relational databases.
although theoretically limited by working memory, none of the interval trees generated and used by absidconvert require more than 300mb of ram on the deployed server, with the majority being rather small in size .
if the data cannot fit into main memory, a method such as that proposed by arge et al.
<cit>  can be used that maintains the interval tree in secondary memory efficiently.
absidconvert is provided as a web page at
http://bioinformatics.louisville.edu/abid/, and is also available as a virtual machine for those wishing to run a local instance.
future work will include providing command line access, a restful interface, and modifying the interface to utilize a workflow management tool for genomic data such as galaxy, where the primary data units are genomic sequences and intervals.
competing interests
the authors declare that they have no competing interests.
author’s contributions
fm was involved in all aspects of the project and was the main code developer.
ecr and jcp designed the overall project goals.
ecr was responsible for directing the project to completion.
rmf played a large role in the project design, identifying sources of genetic entities for inclusion, and the design of the case studies.
bjh provided critical assessment and usability design.
all authors contributed to the preparation of the manuscript.
all authors read and approved the final manuscript.
supplementary material
additional file 1
table containing the ncbi entrez gene symbol and the absidconvert detected gene symbols for  <dig> entrez ids uniquely converted by absidconvert.
click here for file
additional file 2
table containing information on the entrez id, gene symbol, gene type, and ncbi annotation for the  <dig> entrez ids converted by one or more conversion tools missed by absidconvert.
click here for file
additional file 3
table containing information on the entrez id, refseq id, and conversion results for entrez ids correctly converted to refseq ids by madgene that are missed by absidconvert.
click here for file
additional file 4
table containing information on the chromosomal positions found for the five entrez ids that absidconvert is unable to successfully convert to refseq ids.
click here for file
additional file 5
table containing information on the entrez ids converted to refseq ids by david that do not have ncbi annotated refseq entries.
click here for file
additional file 6
table containing information on the  <dig> entrez ids converted exclusively by absidconvert to refseq ids.
thirty-five of the entrez ids are in agreement with ncbi’s entrez annotation.
click here for file
additional file 7
table containing interval and overlapping refseq information for the five entrez ids converted exclusively by absidconvert to refseq ids that are not annotated in ncbi entrez.
click here for file
additional file 8
figure showing the distribution of ensembl transcript lengths for those transcripts either mapped or unmapped by either/both affymetrix®;hg_u133plus <dig>  and agilent cgh105a microarray probes.
click here for file
acknowledgements
this work was partially funded by national institute of health  grants p20rr <dig>  3p20rr016481-09s <dig>  8p20gm103436- <dig> and a department of energy  contract de-em <dig>  partial support was also provided by the paralyzed veterans of america  and by the kentucky spinal cord and head injury research trust .
its contents are solely the responsibility of the authors and do not represent the official views of the funding organizations.

 the nucleic acid research database issue features databases covering various aspects of molecular biology including sequences, gene expression, structures, pathways and diseases. most of these databases are independent of each other and have been created as a result of the respective developers’ domain of interest and resource limitations. due to a lack of standard naming conventions, most of these databases prefer to assign their own custom generated identifiers to the biological entities. major public databases such as genbank and refseq use accession numbers, gene ontology uses a naming convention from organism specific databases, the hugo gene nomenclature committee uses the gene symbol and a custom generated id, entrez uses numeric integers, sequencing projects use systematic names and biologists sometimes use additional aliases. as an example, the breast cancer early onset gene has the official gene symbol of brca provided by hgnc and an associated id ensembl gene id ensg omim id hpr database id refseq id nm_ genbank accession u entrez gene id vega gene id otthumg ucsc gene id uc001uub. uniprot id p and gene aliases fad, fad brcc fancd facd, fancd. fortunately, there is a wealth of information available to the research community in a wide variety of databases. however, it is often difficult to extract or integrate information about a particular biological entity from multiple resources. for instance, a researcher may be interested in extracting functional information spread across different databases for a biological entity such as a gene or a protein; comparing two independent pathways which use different types of identifiers; or comparing results across species, platforms or labs. the lack of a common identifier across these heterogeneous and sometimes redundant biological databases makes the functional analysis of biological data tedious, time consuming, and error prone. one solution to handle heterogeneous databases is to use a global identifier for annotations such as the one described by miriam. miriam requires a global identifier to contain both the data source as well as an internal identifier. for example, urn:miriam:hgnc:brca is composed of urn:miriam that defines the notation to be a urn using the miriam scheme with data type hgnc and identifier brca this method appears promising and has the potential to solve some of the previously mentioned problems, but very few databases follow this standard. another solution is to manually search for these genes one by one in publicly available databases such as entrez, kegg, or geo and infer their functionality. this method is fruitful when the number of genes is small, but is impractical for high throughput experiments, where the number of gene fragments can be on the order of tens of thousands or more. a third solution is to use an id converter tool that uses a database to store all possible annotations where a list of ids may be input as a query which is then converted into the corresponding target ids in a precise and efficient way. one difficulty in the development and maintenance of such conversion tools is the varying granularity of the identifiers. more specifically, the data generated by biological experiments may be at the locus, transcript, sequence or probe level, with varying coverage of a region of interest. this granularity ranges from very fine, at the level of dna microarrays through coarser granularity with sequence reads, transcripts, loci, and chromosomes. it is also possible that annotations at the same level may have different granularities. for example, among dna microarray probes, affymetrix®; probes are usually short whereas agilent probes are longer and cdna probes are generally ≥ nucleotides in length. the relationships between entities at the same or different granularities may be either 1- 1-n, n- or n-m: for example, an affymetrix®; probe may span more than one est; more than one such probe may be contained inside an est; a cdna probe may contain zero, one or more affymetrix®; and agilent probes. another difficulty in the development of such tools is the dynamic nature of annotations. of late, rapid advances in sequencing and their declining costs have enabled researchers to perform novel sequencing as well as resequencing projects. these result in an increased depth of coverage of a genomic sequence, with gaps being filled and repeats more accurately mapped. sometimes, the sequence underlying a genetic entity may change, and on a less frequent basis the whole genomic sequence needs to be updated, and respectively). these changes may modify the structural and functional annotations of a genetic entity. frequent updates in annotations also create problems in the manufacturing of dna microarrays. microarray chips are designed and their probes are annotated using the current build of a specific genome. regardless of the care taken in this design, the system will include flaws due to the combination of the delay inherent in the process of microarray design-manufacture-deployment and the dynamic nature of annotations. attempts to address these problems have been the focus of a number of previous studies. gautlier et al. found redundancies in the annotations of affymetrix®; probes at a sequence level that map to multiple refseq genes. such ambiguities may result in inaccurate interpretations. affyprobeminer uses refseq and genbank’s validated complete coding sequences to regroup the probes on an affymetrix®; chip into consistent probe sets. in their study, regrouping of the probes affected almost 65% of the probes on the hg-u133a chip. harbig et al. reidentified the affymetrix®; u plus genechip®; array probes in an attempt to increase the reproducibility of microarray experiments. they used blast to remap the probes against the genome and redefined approximately 37% of the probes. these studies suggest that redefinition or reorganization of probesets will improve the analytical accuracy of the microarray data, a process that would be greatly facilitated by a means for high-throughput query and mapping/comparison of given sequences to other genomic annotations stored across a wide variety of databases. currently available id conversion tools the problem of id conversion persists even though a number of tools exist to address this problem. some of these are generic and perform id conversion for probes, genes, proteins, and additional annotations while others are more specific to dna microarray probes. organism support varies with many of the tools catering to either a single organism or a small set of comparable species. in addition, cross–species comparison is variable, with most methodologies providing only intra–species conversion. almost every approach uses some sort of relational database with the unique identifier being ensembl ids, refseq ids, or custom generated ids. a brief description of some popular tools follows. david is a web based structural and functional annotation tool to extract biological meaning from a gene list. it uniquely generates custom ids for querying a set of relations and is dependent on annotations from other databases. a component of david, dict, facilitates id conversion. ease, developed by the david bioinformatics team, is a customizable, standalone, windows®; desktop software application, having similar analytic capabilities as that of david. babelomics is an integrated web based tool for structural and functional annotation with an id converter being one of its components. this component uses a universal index linked to ensembl to create a database of species. g:convert, a component of g:profiler, allows arbitrary conversion of genes, proteins and probes into one another. every alias in g:profiler is mapped through a three-level index of gene, transcript and protein ensembl ids. for each index level, all corresponding ids are stored in the database. the hyperlink management system and id converter system automatically updates and maintains hyperlink information among major public biological and chemical databases. it downloads data everyday from authoritative databases and produces a large correspondence table which is used to show the most up-to-date url for genes of interest. users can use cgi programs to create hyperlinks to this data. synergizer assigns a unique internally generated identifier, “peg”, to all external ids that refer to the same biological entity. it mostly uses the ncbi “gene2accession” file to maintain a database of synonym relationships and produce a simple web interface. madgene uses correspondence tables and allows conversions in an efficient way. the clone/gene id converter, matchminer, the gene name converter in genemerge, resourcerer and genelynx are additional id conversion tools. some of the id conversion tools are more specific, such as those that work only at the probe level. gatexplorer is a web based tool for analysis and visualization of affymetrix®; probes at the genomic and transcriptomic level. it performs de–novo mapping of all the probes of affymetrix®;’s expression and exon arrays against the transcriptome of the corresponding organism using blast and records the coordinates on the genome. unmapped probes are mapped to an ncrna database downloaded from rnadb. only the perfect match alignment is selected while mapping these probes. the location of a gene or probe on the genome can be visualized along with all the transcripts present in that region. netaffx™, provided by affymetrix®;, performs id conversion of affymetrix®; probes for different organisms and has a feature to perform structural and functional annotation. plandbaffy is a probe-level annotation database for affymetrix®; microarrays that uses blat to map individual probes onto the human genome. these probes are then annotated using information extracted from refseq. probematchdb uses a number of public databases to perform cross-species and cross-platform probe mapping. the database conversions are enabled by unigene and homologene identifiers. uniprot’s id mapping tool works on the gene and protein level and converts gene ids into uniprot ids and vice versa. some software tools have unique methods for mapping between different ids. onto–translate converts one type of ids into another by calculating the optimal path between ids, taking into account the “trustworthiness” of data contained in various databases. the aliasserver uses a custom generated unique 64-bit reference identifier which is computed from the amino acid sequence using the crc algorithm where each id is a unique combination of species identifier, type of database and the id itself. some databases/tools aid in id conversion but do not function as a full fledged id conversion tool. biomart, earlier known as ensmart, provides a web and api interface to download data such as go terms, genes, transcripts and expression arrays from different databases using filters. bridgedb provides an interface to connect bioinformatics tools such as cytoscape, pathvisio, or wikipathways with other mapping services such as ensembl, picr, and any local database or text files. it is intended to be used by bioinformatics developers and works on the novel idea of mapping custom identifiers to established identifiers such as ensembl id and then relies on ensembl to provide the rest of the conversion. side by side feature comparisons of these tools are provided in table data sources for select tools are listed in table aabbreviations: annot. view: custom annotation view, annot.: annotation, org.: organisms, prots: proteins, affy: affymetrix®;, trans: transcripts, seqs: sequences, ens.: ensembl, corr: correspondence, acc: accession, bio: biological, na: not applicable, cnd: could not determine, ⇓:download knowledgebase, vm: virtual machine. drawbacks associated with existing approaches most of the id conversion tools mentioned above use a two step conversion method. to convert an id “a” to id “b”, the first step is to use a correspondence annotation relation or table to find a common intermediary id “c”. this common id “c” is then converted into target id “b” using another correspondence table. some tools use ensembl or refseq as an intermediary while others generate unique custom identifiers. for example, the clone/gene id converter and gatexplorer use ensembl id, plandbaffy uses refseq whereas david and synergizer use a custom generated david id and peg respectively. these tools convert smaller fragments into coarser genetic entities using inferred annotation level information irrespective of the fact that these small fragments may not be representative of the annotation as a whole. these methodologies also tend to lose structural and other information available at the probe or sequence level. as stated previously, annotations are dynamic and databases such as ensembl and refseq are updated daily making it difficult to keep the databases of id conversion tools current. this is more problematic when the intermediate ids are custom generated as these require more effort to update. most of the tools are based on a relational database and the dynamic nature of annotations may introduce database anomalies because of the frequent insertion, deletion and updating of the annotations. if a gene is discovered, deleted or updated in any of these databases, or the annotations corresponding to an entity are added, deleted or updated, then all the databases or correspondence tables also need to be updated. in the case of microarray experiments, if a probe corresponds to a recently deleted entity then that probe annotation needs to be edited as well. updating any of these authoritative databases may induce a chain-reaction for any other systems using that information and any experimental result deduced from the updated probe may become invalid. those tools that generate their own unique identifier such as david, synergizer or babelomics, although efficient, face a similar situation and need to be updated frequently. as updating an annotation database is labor and resource intensive, some of the tools cannot afford to update their knowledgebase regularly. absolute method for id conversion a feature of biological entities that is currently ignored in id conversion is the sequence mapping information. for species where a reference genome is available, all nucleic acid and protein-based annotations, no matter the granularity, can be aligned to that reference genome sequence and therefore annotated by genomic intervals. once the absolute genomic coordinates on a reference genome for all entities have been determined, these can be queried to find all overlapping entities, thus performing id conversion. this conversion uses the same two step method as adopted by most of the id conversion tools, considering the genomic coordinates as the basis of conversion, rather than the annotation level information used by other tools. compared to other types of intermediate ids, the intervals on a reference genome sequence are relatively static, and remapping of entities to modified genomic sequences is relatively trivial, making it possible to easily update the system. using interval trees, conversion by finding overlapping intervals is fast and efficient. figure shows the steps to perform sequence-based or absolute id conversion. in the figure, all transcripts corresponding to probe a are being found. the first step in this conversion is to find the genomic coordinates corresponding to probe a and the second step is to find all transcripts that span those coordinates. in this example transcript and transcript are the converted ids corresponding to the probe a. transcript is not represented by probe a as the underlying genomic sequence is not part of transcript subsequent sections describe the design and implementation of a genomic interval based id conversion tool, absidconvert. methods the design of absidconvert was accomplished using a preprocessing and a query step. in the preprocessing step, reference genomes were downloaded from the ucsc genome browser and the ncbi website. the sequence information for a variety of identifiers at different granularities such as probes, sequences, transcripts and genes were downloaded from their respective authoritative websites or ucsc. the identifier types include affymetrix®; probes, agilent probes, est sequences, ensembl transcripts and entrez genes. each identifier sequence was mapped to the respective genome using either blat or bowtie. blat was used to map longer sequences, while bowtie was used for relatively short sequences such as affymetrix®; and agilent probes. each identifier was then annotated with structural information such as start, end, size and chrom. this information was collected for each identifier as a genomic interval. genetic entities with multiple exons such as transcripts were treated differently as there are two ways in which these can be structurally annotated. one method is to use the extreme ends as their intervals including both the exons as well as intronic regions, or alternatively exclude the intronic regions and assume the transcript’s genomic intervals are an assembly of genomic intervals of the participating exons. finally organism and identifier type specific interval trees were constructed and stored. a list of all identifiers and their type was also stored in a relational database to facilitate batch look-up for the types of identifiers. figure shows the design steps of absidconvert. once structural annotation for each of the identifiers is available, absidconvert can query this information. this query step uses the structural annotation information of each identifier and the organism specific database generated from the previous step. absidconvert assumes two biological entities are the same if their genomic sequences are also the same, overlap or one is contained within the other. as the number of annotations are large and frequent insertions and deletions are routine, an efficient data structure for storage and computational operations is needed. considering that the structural annotation is in the form of genomic intervals, a modified red-black tree, known as an interval tree, is used to store the information for all ids. an interval tree maintains a dynamic set of elements, with each element x containing an interval int. this int stores the start and end of the interval apart from other auxiliary information. this data structure is dynamic in nature and can perform insertions and deletions efficiently in time o, where n is the number of elements. interval trees have been shown to be efficient for working with a large number of genomic intervals. there are four possible ways in which absidconvert may be queried: • lookup identifiers: given a mixed list of identifiers, absidconvert can determine the types of identifiers in the list. this step uses the relational database created in the preprocessing step and can efficiently categorize the ids in the list. • batch conversion of ids: given a list of identifiers, absidconvert uses the interval tree to find their genomic coordinates. once the coordinate information is available, all overlapping identifiers can be found by querying the interval tree. this uses the iranges and genomicranges packages internally to maintain the genomic intervals which are based on allen’s interval algebra. users can specify various range parameters using the interface. the overlap type parameter may take any one of ‘any’, ‘start’, ‘end’, ‘equal’ or ‘within’ as its value. by default ‘any’ overlap is accepted. if ‘type’ value is ‘start’ or ‘end’ then the query intervals are required to have matching ‘start’ and ‘end’ respectively with subject intervals in the database. if ‘type’ is ‘equal’ then only those subjects are retrieved which have the exact same coordinates. for ‘within’, the query must be contained wholly within the subject intervals. another parameter is for specifying the maximum gap between subject and query intervals to consider them as overlapping. the default value is zero which assumes there should not be any gap between the subject and query intervals. this parameter is useful for finding genes in the flanking regions of the specified intervals. the third parameter is the minimum overlap size that specifies the minimum number of overlapping base pairs needed to consider the query and subject an overlap. the default overlap value is one. the last parameter is the ‘select’ parameter that specifies which type of overlaps will be reported. by default, all overlapping intervals will be reported. selecting ‘first’, ‘last’ and ‘arbitrary’ will report first, last and arbitrary overlapping intervals from the result. a simple example using intervals is shown in figure in this case, the reference genome is bp long. the subject database contain four intervals s s s and s that represent the interval database. query intervals also consist of four intervals q q q qnd q considering default values for range parameters, q overlaps with s q and q overlap with all the intervals in the subject, whereas q overlaps with s s and s if the values of the parameters are type=‘within’, maxgap = minoverlap= select= ‘all’ then q overlaps with s q with s and q with s and s if the values of the parameters are type=‘end’, maxgap = minoverlap = select= ‘all’ then q overlaps with s q with s and q and q with s • intervals as input to absidconvert: a unique feature of the id conversion is to find target identifiers corresponding to a given interval. for example, next-generation sequencers generally map the dna sequences or reads to a reference genome and output the intervals for each aligned reads. finding desired target identifiers corresponding to these intervals is routinely required. absidconvert efficiently converts these coordinates into target identifiers in a high throughput manner. for instance, a user of absidconvert is able to take a set of intervals upstream of a set of transcription start sites to determine if any features are annotated proximal to the regions of interest. • sequences as input to absidconvert: sometimes a user may be interested in finding all identifiers that correspond to a particular sequence or a list of sequences. for instance, a user may be interested in finding all gene names and entrez ids corresponding to a set of sequences. in this case, absidconvert maps these sequences to the corresponding genome and determines the genomic intervals they belong to and then retrieves all the desired target identifiers that overlap these intervals. due to the computational complexity involved in mapping long sequences using a generic mapping algorithm such as blat or blast, the web version of absidconvert supports only short sequence mapping using bowtie. longer sequences can be mapped using blat in the virtual machine version of absidconvert. sequence output from next-generation sequencing technologies can be catered efficiently using absidconvert. alternatively, the coordinate information may be obtained by submitting the sequences to galaxy or the ucsc genome browser and subsequently inputting the intervals using absidconvert. mapping parameters can be specified by the user through the interface. parameters include the maximum number of mismatches which can range from zero to three. the second mapping parameter specifies which type of alignments are to be reported. the default value is ‘all best’ in which all best alignments will be reported by bowtie. however, ‘all’, ‘k’ or ‘k best’ can be selected for bowtie output. absidconvert also has another parameter ‘do not report ’ that takes a positive integer value which specifies that bowtie will suppress all alignments for a particular read if the total number of reportable alignments for that read is more than the specified value. the default value of - specifies that all alignments will be accepted. for instance, if this value is set to then bowtie will suppress all those alignments for reads that map to or more locations on the genome. this is an effective option to mask repeat sequences or small sequences from appearing into the output because their probability to map at multiple locations on the genome is higher. absidconvert supports major species for performing id conversion on a list of identifiers and a list of intervals. it also has sequence level mapping support for major species including homo sapiens, mus musculus, rattus norvegicus, bos taurus, gallus gallus, sus scrofa, xenopus tropicalis, anopheles gambiae, drosophila melanogaster, caenorhabditis elegans, saccharomyces cerevisiae, and danio rerio. absidconvert converts the input into target identifiers with links to authoritative databases. all intermediate interval files are available to download for later use. it also generates custom annotation files that can be used to view the ids simultaneously as a custom track in the ucsc genome browser. the performance and potential uses for absidconvert are discussed in the following sections.  intervals vs. relational database the genomic coordinate information for different identifier types mapped to species were stored as intervals. an interval tree method was implemented and used to store and query the corresponding interval information for each identifier type. for comparison with relational databases, an equivalent mysql database was implemented to perform id conversion based on coordinate information, and the run time for both of these methods were compared. run–time comparisons of the interval tree and mysql implementations were performed using randomly sampled rat est ids which were subsequently converted to entrez gene ids. to test the actual runtime, the number of est ids was increased exponentially for each test point and the corresponding execution time was measured. the run time complexity of the interval tree maintained a constant rate while the relational methodology grows in linear fashion, allowing for the conversion of millions of identifiers in only a few seconds. further analysis of conversion runtime was performed using random sampled ids from affymetrix®; rat230_ microarray probes, agilent cgh105a microarray probes, refseq ids, ensembl transcripts, entrez genes, hugo gene symbols and est ids which were converted into one another using the web version of absidconvert. the extreme left column represents the source identifiers which are converted to target identifiers shown in first row. the numbers in small parentheses in the first row show the total number of genomic coordinates for individual id types. since absidconvert supports conversion to multiple target types, the last column represents the time elapsed when an input type is converted into all other id types. run–time comparison direct comparison to other id conversion approaches is not straightforward due to the differences in annotation information, supported id types, and development/deployment platforms. in order to test the runtime of comparable solutions, a varying number of affymetrix®; rat230_ microarray probesets were converted to entrez ids. when the number of probe sets converted was small, the conversion time for all tools was nominal. for a moderate number of probe sets madgene, david and absidconvert performed similarly, while gatexplorer took around a minute and clone/gene id converter took minutes ). as the number of probe sets further increased, all of the tools, with the exception of madgene and absidconvert, were incapable of tractably handling such a large number of inputs. since the affymetrix®; rat230_ has roughly unique probe sets and over individual perfect match probes, a run time comparison for a large number of inputs was performed by converting randomly sampled human transcripts into entrez ids. for inputs, only madgene and absidconvert completed successfully, taking sec and sec, respectively ). the run–time complexity for absidconvert compares favorably to other similar tools, demonstrating its applicability in the analysis of high throughput data. output accuracy the accuracy of conversions performed using absidconvert was assessed based on the overlap of the successfully converted ids with those found using other tools for three types of conversions. in the first conversion, unique entrez ids were randomly sampled from the “org.hs.eg.db” bioconductor annotation package and converted to their corresponding official gene symbols. ten id conversion tools, from a total of tools listed in table can perform this conversion. considering ncbi as the authority for entrez ids, the accuracy of different conversion tools were evaluated using the following assumptions: ncbi contains the most up to date information and its annotations are correct. an entrez id may be annotated by more than one gene symbol. given an entrez id x, if a tool converts x to a set of gene symbols, y, and ncbi annotates x to another set of gene symbols, z, then accuracy terms can be defined as: • true positives are those conversions in which the converted gene symbol set contains all the gene symbol annotated by ncbi. • false positives are unexpected results. this includes incorrect conversions, as well as those conversions in which ncbi does not annotate an entrez id with any gene symbol, but a tool finds some gene symbol corresponding to that entrez id. • false negatives are missing conversions in which a tool could not find corresponding gene symbol. • true negatives are the correct absence of conversion in which ncbi as well as a particular tool does not convert an entrez to any gene symbol. accuracy is defined as %accuracy=tp+tntp+tn+fp+fn× table shows the contingency table and associated statistics for the conversion of entrez ids to gene symbols. absidconvert converted a total of entrez ids with an accuracy of % followed by david, madgene and hms & ic. although onto-translate converted a total of entrez ids, it has more fp conversions than hms & ic and therefore a lower accuracy. we further investigated the conversions from the top four tools on the basis of their accuracy and summarized the results in a venn diagram ). absidconvert converted a total of entrez ids which are missed by the other tools. ncbi places all these entrez ids onto the reference genome and annotates them with gene symbols that are in agreement with absidconvert. of these entrez ids, are categorized as “pseudo”, as “miscrna”, four as “protein-coding”, three as “unknown” and one as “other”. absidconvert was unable to convert a total of entrez ids, out of which ids were not converted by any of the tools examined. of the entrez ids that absidconvert was not able to convert but other tools were, most were either “not on current assembly”, meaning that the reference sequence for that entrez id could not be mapped to the current genome, but could be mapped to previous genome assemblies; or “not annotated on reference assembly”, indicating that the sequence cannot be found on the reference assembly at all. five conversions were found where the entrez ids reported had since been deleted and replaced. in a second conversion test, randomly sampled entrez ids were converted to refseq ids using ten of the tools listed in table. there are many different classes of refseq ids, including mrna, rna, protein, as well as predicted versions of each one. how refseq ids are segregated for conversion differs among the tools tested. for example, a number of tools combine all the different types of refseq ids into one converted id type while others treat each one separately. other tools ignore the predicted refseq ids and only consider mrna and rna. for example, absidconvert’s refseq database combines both mrna and rna, whereas madgene includes predicted products. david and synergizer have separate options for rna and mrna refseq. therefore, to enable comparison between all the tools, only those conversions that result in mrna or rna refseq ids are considered, and for those tools that report them separately, the results from both conversions were combined. in addition, any predicted refseq ids were removed. using the same assumptions as reported for the entrez to symbol conversion, the accuracy of conversion for each tool was calculated. of the entrez ids used, ncbi annotates only with one or more refseq. in this case, the accuracy for the various tools ranged from a high of % to a low of %. the results from the four most accurate tools were investigated further. entrez ids were converted commonly by all tools ). absidconvert converted followed by madgene, david and onto-translate. five conversions specific to madgene were not found by absidconvert. in this case, absidconvert correctly mapped the entrez ids to the genome; however, the corresponding refseq ids were not in the data obtained from ucsc. other conversions that absidconvert did not report were found to be false positives reported by other tools. for example, david and onto-translate both reported converting “4586” to “nm_017511” and “441956” to “nm_001013729”; however, the genomic intervals for those ids do not overlap, and both refseq ids are shown in ncbi as “permanently suppressed”. for the twenty conversions specific to david, the reported refseq ids were found to be associated with different entrez ids in ncbi. the thirty-eight entrez ids converted only by absidconvert were investigated further to verify whether they were “correct”. thirty-three are in agreement with the ncbi data. for the other five, we examined the genomic intervals of both the entrez ids and reported refseq ids to verify that they do indeed overlap. in all cases the converted ids do have overlapping intervals with two of the entrez ids discontinued and replaced since the initial construction of the absidconvert database, “100505905” and “100652874”. to better assess the accuracy of absidconvert compared to other tools, the entrez to refseq id conversion was repeated ten times, randomly choosing entrez ids each time. out of the randomly selected entrez ids, were unique. absidconvert converted, followed by madgene, david and onto-translate ). a total of of the ids were exclusively converted by absidconvert. in the third conversion, randomly sampled human affymetrix®; genechip hg-u plus probesets were converted to agilent cgh44b probes ). this type of cross-platform conversion is important in meta-analysis studies where results are drawn by integrating and analyzing data from a number of independent studies/platforms. as this type of conversion is available only in synergizer, we compared the conversion results of this tool with absidconvert. synergizer converted whereas absidconvert converted probesets. the reason for the small number of conversions is primarily due to the design differences of the probes on these chips. two questions required deeper investigation: why was absidconvert not able to convert affymetrix®; ids that were successfully converted by synergizer; and are the conversions exclusive to absidconvert valid? to answer these, we extracted the design annotation of all the affymetrix®; genechip hg-u plus probesets provided by affymetrix’s netaffx along with the design annotations for the agilent cgh44b probes supplied by agilent. these provided the individual locations of each probe on the hg genome, thereby enabling investigation of the interval separation between the probesets. in order to examine the probesets converted by synergizer but not by absidconvert, the genomic location of the affymetrix®; probesets were compared to the genomic locations of the agilent probes. fifty-six of the probes are separated according to their genomic locations and do not overlap at all. this separation ranges from to bp with a median separation of bases. further analysis determines that these all lie in the regions between the individual probes of the respective probesets and therefore have no shared sequence identity. most of the id converter tools including synergizer map the genetic entities spanning tens of bases to an intermediary such as ensembl that is at a coarser granularity spanning a few kilobases with possible intronic regions. while performing conversions, these tools only use the probe annotation, disregarding the actual sequence information. the above false positives provided by synergizer are likely the result of ignoring the sequence level information as the two types of probes actually span different genomic intervals. next we considered conversions found exclusively by absidconvert. based on the official annotation from netaffx™, we found that intervals for all affymetrix®; probesets actually contain or overlap the converted agilent probes with a mean overlap of bases. considering that most of the agilent probes are bases long and an affymetrix®; probeset contains overlapping bp probes, this indicates most of these agilent probes are contained in the affymetrix®; probeset region. these probesets were checked at the probe level and it was determined that these converted agilent probes overlap with individual affymetrix®; probes to some extent, or are completely contained with a mean overlap length of bp. we are not sure why synergizer was unable to convert these probes; however, the official annotation confirms these annotations and bolsters our confidence in the power and accuracy of our sequence based id conversion. case studies three illustrative case studies were explored to demonstrate the capabilities of absidconvert. the first case study considers sequence-based mapping of identifiers in a comparative genomics analysis of organisms involved in malaria; the second examines remapping of probes to annotations within and across species using a historical cdna platform from incyte; and the third identifies ensembl transcripts mapped by agilent and affymetrix®; arrays. case study 1: comparative genomics: plasmodium mapped to human and anopheles gambiae recent studies have surveyed the role of both host and pathogen genetic variability to determine molecular signatures for host-pathogen interactions. while the interactions between a pathogen and its host are often mediated by the host immune system responses to the pathogen, host-pathogen relationships theoretically have the potential to create a metagenomic environment whereby the total transcriptome is contributed by both the host and pathogen genes. in some cases, such as neisseria meningitidis, a direct interaction between host and pathogen genes has been demonstrated. as an illustrative example, it might be possible that shared sequence similarities between pathogen and host genes play a role in host gene regulation via pathogen genes and gene products that provide additional promoter sites, mirna targets, and binding motifs similar to those found in the host. to test the feasibility of this possibility in the context of malaria, we used absidconvert to identify coding sequences identical between the plasmodium falciparum and plasmodium vivax species and the human and anopheles genomes. plasmodium is a parasite responsible for causing malaria in humans primarily in tropical and sub–tropical areas. about billion people are at risk of this disease, leading to million malaria cases and one million deaths worldwide every year. altogether four plasmodium species are responsible which are carried by the female anopheles gambiae mosquito. pf and pv are the most common, with pf being the deadliest. coding sequences for each gene for these two species were downloaded from the plasmodb website. the total number of coding sequences in pf and pv were and respectively. sequences for each of these genes were then fragmented into base-pair long sequences with an overlap of bp. the fragmented sequences were given a unique name by attaching a numerical suffix onto the gene name that denotes the order of appearance in the gene sequence. these fragmented sequences were analyzed using absidconvert by selecting default parameters including no mismatch while aligning to the anopheles gambiae and homo sapiens genomes. a total of gene fragments from pf ) had an exact sequence match to human genes ). for pv, the aligned number of gene fragments and corresponding genes were ) and ), respectively. these numbers indicate that the gene fragments align to multiple locations on the human genome. among genes that were mapped from pf and pv gene fragments, a total of genes were common. when the same gene fragment sequences from pf and pv were aligned to the anopheles gambiae genome, a total of ) gene fragments from pf were mapped to ) different genes, showing that the correspondence between the gene fragments and genes is largely one–to–one. these numbers for pv were ) and ), respectively. a more detailed analysis of the genes identified using ontological information indicates a significant enrichment in cell adhesion processes. these are present in the go terms ‘cell-cell adhesion’, but also implied by the large number of terms regarding neuronal axonogenesis and synapse formation, which require specific regulation of cellular adhesion. while purely speculative at this point, it is possible these plasmodium genes interact with the human host to help sequester human erythrocytes in small blood vessels which aids in the invasion plasmodium into the immune system. while benchtop analysis of these genes is needed to determine if the “feasible” actually occurs, it is clear that analysis using absidconvert has identified, via cross-species analysis, a limited set of genes that can be further interrogated for understanding the malaria-related pathophysiology, including the process of plasmodium incorporation into erythrocytes. case study 2: reinterpretation of prior datasets annotations used for dna microarray studies quickly become out–of–date as more knowledge emerges about a species’ transcriptome. in addition, there are instances where one microarray platform may be used to measure gene products from a comparative species. for example, incyte arrays spotted with human ests have been used to query gene expression levels in mouse and/or rat, based on the assumption that the human ests would bind to and provide measurements of the corresponding gene in rodents. using the original est sequences spotted on the array from these studies, we sought to verify the current annotations of the ests, and also determine which rodent genes should bind the ests based on sequence alignment to the human, mouse, and rat genomes. original est sequences were found by searching two sources using the incyte ids supplied on the chip. the first source was the ncbi est database, using a search string composed of “image:” and the incyte clone id number. the second source was the open biosystems database, using a search string composed of “lifeseq” and the clone id number. in some instances, multiple est sequences were returned for each clone id. a total of sequences were downloaded and aligned to the genomes of human, rat, and mouse using absidconvert with the default blat settings. the genome wide best alignment was found for each probe by considering only those alignments falling within 5% of the maximal alignment score ). corresponding to each of these aligned coordinates, overlapping entrez ids were found for all three organisms. out of the human incyte ids which had corresponding genomic interval, have at least one human entrez id associated with them. this number was for mouse and for rat ). homologous genes can be compared across species using ncbi’s homologene resource when gene names are known. however, if sequence information is available, it would be best to use that sequence information to determine if homology exists based on sequence conservation, particularly in cases where probes of known sequence are being used to measure a specific gene, such as in dna microarrays or in–situ hybridization. both methodologies were applied to the incyte array used in. for the homologene based comparison, all of the incyte ids that map to at least one entrez id using absidconvert were used to determine if a homologous gene exists, and if so, if there are corresponding entries for each of the species studied. similarly, for those incyte probes matching at least one entrez id, the sequence was used as a query into each of the other species using absidconvert to determine if the probe maps to and overlaps an entrez id in a cross-species sense. as table indicates, using the homologene conversion alone yields a high number of homologs; however, using the sequence level information, it can be seen that a much lower percentage of probes actually map to known entrez gene regions in the other species. these demonstrate that only a small number of the probes on the array should be utilized for cross species comparisons. amapped†:number of probes mapped to genome; entrez‡:mapped probes with entrez id; homolÂ§: probes with entrez id as well as homologene id; hom: homologene based homologs; seq: sequence based homologs determined using absidconvert. case study 3: meta–analytic studies across platforms meta-analysis enables the integration of many different experiments with a common research hypothesis. however, high-throughput -omics meta-analyses are hindered due to the heterogeneity of dna microarray array designs, data acquisition, analysis, and inter- and intra-study variability. therefore, many meta-analyses use the same species or even the same array platform to mitigate some of these heterogeneities. however, many studies do still attempt to perform cross-platform and inter-species meta-analyses, and tools such as ailun, a-madman, and lola enable cross-species meta-analysis using entrez id, gene symbol or other ids as a conversion intermediary. absidconvert can perform cross-platform/-species analysis efficiently using the sequence based approach. we previously demonstrated that absidconvert efficiently and accurately converted affymetrix®; hg_u133plus probes into agilent cgh105a probes, among other types of conversions. to determine how comparable two microarray studies using different array platforms on a common organism could be, affymetrix®; hg_u133plus and agilent cgh105a probe sequences were mapped and converted to corresponding human ensembl transcripts using the default absidconvert parameters. for the affymetrix platform, out of probes were mapped to one or more transcripts, with of the total ensembl transcripts being mapped. this leaves ensembl transcripts that were not mapped by any affymetrix®; probes. for agilent, mapped to ensembl transcripts. ensembl transcripts do not have any mapped agilent cgh105a probes. the number of shared ensembl transcripts between platforms was surprisingly small, indicating that each platform appears to have probe specific subsets of ensembl transcripts. the number of ensembl transcripts not probed by either platform was surprisingly large. this appears to be due to a lack of probes designed to bind those ensembl transcripts, as the majority of unmapped transcripts are much shorter than those that are mapped. as figure illustrates, transcripts should be directly comparable between affymetrix®; hg_u133plus and agilent cgh105a, while a large number of transcripts are not available in one or the other platforms.  absidconvert is the only known gene id conversion tool based on genomic coordinates/intervals of which we are aware. this is a novel and important contribution in the realm of gene id conversion due to the large variety of genetic entities in current use by biologists, the need to convert between them, and the fact that most biological entities have an associated sequence. mapping of the entity sequence to a reference genome sequence provides the concomitant genomic interval that allows determination of other entities that have overlapping genomic intervals. the interval basis of absidconvert provides ease of flexibility with respect to any additions, deletions or updates of the underlying objects, requiring only adding of intervals, removing intervals, or modifying the intervals themselves, respectively. this makes it possible to easily keep the structure updated as the current state of biological knowledge changes. a major update is only required when the underlying genome changes, a fairly rare occurrence for most organisms, especially when compared to how often other genomic databases are modified. these intervals also allow easy discovery of genetic entities that only partially overlap with queried ids/intervals, or that are within a specified distance nearby. more frequently, researchers are interested in those genes that are near specific genomic intervals corresponding to various types of genetic control elements such as transcription factor binding sites, enhancers, untranslated regions, and hyper/hypo methylated regions. absidconvert makes it easy to find those entities that overlap or lie nearby regions of interest. with the incorporation of a sequence mapping algorithm, absidconvert integrates the determination of genomic intervals for any supplied sequence, making it possible to easily find and convert between ids from any platform and organism, such as the examination of correspondence of the human est clones with rat and mouse genes and of plasmodium and human genes. we do not know of any other system that can easily accomplish these types of analyses. absidconvert can greatly facilitate the work of those who are involved in meta analyses studies. when comparing studies where either the species and / or platform varies, this methodology will have clear advantages over others as it is based on common genomic coordinates. the use of an interval tree structure makes it possible to perform large conversions quickly and efficiently. this method is efficient while dealing with genomic intervals and has a significant advantage over other methods such as relational databases. although theoretically limited by working memory, none of the interval trees generated and used by absidconvert require more than 300mb of ram on the deployed server, with the majority being rather small in size. if the data cannot fit into main memory, a method such as that proposed by arge et al. can be used that maintains the interval tree in secondary memory efficiently. absidconvert is provided as a web page at http://bioinformatics.louisville.edu/abid/, and is also available as a virtual machine for those wishing to run a local instance. future work will include providing command line access, a restful interface, and modifying the interface to utilize a workflow management tool for genomic data such as galaxy, where the primary data units are genomic sequences and intervals. competing interests the authors declare that they have no competing interests. author’s contributions fm was involved in all aspects of the project and was the main code developer. ecr and jcp designed the overall project goals. ecr was responsible for directing the project to completion. rmf played a large role in the project design, identifying sources of genetic entities for inclusion, and the design of the case studies. bjh provided critical assessment and usability design. all authors contributed to the preparation of the manuscript. all authors read and approved the final manuscript. supplementary material additional file 1 table containing the ncbi entrez gene symbol and the absidconvert detected gene symbols for entrez ids uniquely converted by absidconvert. click here for file additional file 2 table containing information on the entrez id, gene symbol, gene type, and ncbi annotation for the entrez ids converted by one or more conversion tools missed by absidconvert. click here for file additional file 3 table containing information on the entrez id, refseq id, and conversion results for entrez ids correctly converted to refseq ids by madgene that are missed by absidconvert. click here for file additional file 4 table containing information on the chromosomal positions found for the five entrez ids that absidconvert is unable to successfully convert to refseq ids. click here for file additional file 5 table containing information on the entrez ids converted to refseq ids by david that do not have ncbi annotated refseq entries. click here for file additional file 6 table containing information on the entrez ids converted exclusively by absidconvert to refseq ids. thirty-five of the entrez ids are in agreement with ncbi’s entrez annotation. click here for file additional file 7 table containing interval and overlapping refseq information for the five entrez ids converted exclusively by absidconvert to refseq ids that are not annotated in ncbi entrez. click here for file additional file 8 figure showing the distribution of ensembl transcript lengths for those transcripts either mapped or unmapped by either/both affymetrix®;hg_u133plus and agilent cgh105a microarray probes. click here for file acknowledgements this work was partially funded by national institute of health grants p20rr 3p20rr016481-09s 8p20gm103436- and a department of energy contract de-em partial support was also provided by the paralyzed veterans of america and by the kentucky spinal cord and head injury research trust. its contents are solely the responsibility of the authors and do not represent the official views of the funding organizations.
we have developed absidconvert, a methodology for converting between genomic identifiers by first mapping them onto a common universal coordinate system using an interval tree which is subsequently queried for overlapping identifiers. annotationgene id conversionmeta-analysisgenomic rangeinterval treescomparative analysisgranularityuniversal identifierabsidconvert absidconvert is freely available as a web application or downloadable as a virtual machine at: all annotations, no matter the granularity, can be aligned to genomic sequences and therefore annotated by genomic intervals. absidconvert has many potential uses, including gene identifier conversion, identification of features within a genomic region, and cross-species comparisons. the utility is demonstrated in three case studies: 1) comparative genomic study mapping plasmodium gene sequences to corresponding human and mosquito transcriptional regions; 2) cross-species study of incyte clone sequences; and 3) analysis of human ensembl transcripts mapped by affymetrix®; and agilent microarray probes. absidconvert currently supports id conversion of species for a given list of input identifiers, genomic sequence, or genome intervals. existing bioinformatic methodologies categorize and compare these elements using inferred descriptive annotation given this sequence information irrespective of the fact that it may not be representative of the identifier as a whole.
 high-throughput molecular biology techniques yield vast amounts of data, often by detecting small portions of ribonucleotides corresponding to specific identifiers. existing bioinformatic methodologies categorize and compare these elements using inferred descriptive annotation given this sequence information irrespective of the fact that it may not be representative of the identifier as a whole.  all annotations, no matter the granularity, can be aligned to genomic sequences and therefore annotated by genomic intervals. we have developed absidconvert, a methodology for converting between genomic identifiers by first mapping them onto a common universal coordinate system using an interval tree which is subsequently queried for overlapping identifiers. absidconvert has many potential uses, including gene identifier conversion, identification of features within a genomic region, and cross-species comparisons. the utility is demonstrated in three case studies: 1) comparative genomic study mapping plasmodium gene sequences to corresponding human and mosquito transcriptional regions; 2) cross-species study of incyte clone sequences; and 3) analysis of human ensembl transcripts mapped by affymetrix®; and agilent microarray probes. absidconvert currently supports id conversion of species for a given list of input identifiers, genomic sequence, or genome intervals.  absidconvert provides an efficient and reliable mechanism for conversion between identifier domains of interest. the flexibility of this tool allows for custom definition identifier domains contingent upon the availability and determination of a genomic mapping interval. as the genomes and the sequences for genetic elements are further refined, this tool will become increasingly useful and accurate. absidconvert is freely available as a web application or downloadable as a virtual machine at: http://bioinformatics.louisville.edu/abid/. annotationgene id conversionmeta-analysisgenomic rangeinterval treescomparative analysisgranularityuniversal identifierabsidconvert 