BACKGROUND
inferring the evolution of gene families, the phylogeny of species, and tracing the biogeography of populations depend on reliable delineation of orthologous genes and paralogous copies of them.
while delineation and identification of orthologous and paralogous genes has been firmly established for studying genomic data , few approaches are currently available for assessing transcripts in the same manner .
each of these approaches exhibits, and suffers from, specific problems, potentially leading to erroneous species and gene tree inference .
we developed a novel software pipeline, called orthograph, for convenient, fast, and reliable identification of orthologous  nucleotide or amino acid sequences, which resolves existing algorithmic and software-technical issues.
orthograph builds on previously proposed graph-based clustering algorithms, but extends them without sacrificing accuracy or computational speed.
when comparing the gene repertoires of species, one of the first analytical steps is the delineation of orthologous genes , i.e., the identification of genes that originated from a single gene in the last common ancestor of the compared species.
each of the delineated orthologous groups  can also include species- or lineage-specific gene copies , that evolved by gene duplication after the evolutionary split of the ancestor into different species  <cit> .
finally, horizontal gene transfer can give rise to xenologous gene copies  from a single ancestral gene  <cit> .
two fundamentally different approaches to identify potential orthologs, paralogs, and xenologs have been established: tree-based and graph-based approaches.
the benefit of graph-based approaches, which we will subsequently focus on, is their computational efficiency and scalability .
in general, graph-based approaches assessing gene orthology make use of the genome-wide best reciprocal hit  criterion.
it rests on the assumption that orthologs in two genomes are more similar to each other than to any other gene in the compared genomes, since they are direct and exclusive descendants from a single ancestral gene  <cit> .
various graph-based approaches based on the brh criterion have been developed that de novo infer orthology among genes and proteins in the gene or protein sets of sequenced and annotated organisms, such as orthomcl  <cit> , coco-cl  <cit> , orthodb  <cit> , inparanoid  <cit> , orthofinder  <cit> , and oma  <cit> .
the reliability of these methods critically depend on the fact that differential gene loss is the exception and that gene or protein repertoires are complete.
this means that in order to apply a graph-based approach to infer gene orthology among genomes, the organisms’ gene or protein repertoire must be reliably known.
these methods are therefore not appropriate for assessing orthology among nucleotide sequences in sequenced transcriptomes, since transcript libraries contain only a subset of the organisms’ actual gene repertoire.
the nucleotide sequence of a gene may be missing in a given transcript library simply because the gene was not  expressed at the time of rna preservation.
given that transcriptome sequencing represents an extremely valuable and cost-efficient strategy to sample coding nucleotide sequences of a large fraction of an organism’s gene repertoire  <cit> , several graph-based approaches have been developed that are dedicated to ortholog identification in transcript libraries.
a possible solution to the aforementioned problem in transcript orthology assessment is to assign transcripts to ogs whose genealogical relationships have already been reliably inferred, rather than to infer orthology of these genes de novo from the transcripts.
knowledge of the genealogical relationships of genes can be derived from comparative genomic analyses and may be retrievable from public databases such as orthodb  <cit> .
this approach has been implemented in orthoselect  <cit>  and hamstr  <cit> .
however, orthoselect does not implement the brh criterion, but a unidirectional search.
orthoselect is thus prone to false positives.
hamstr, on the other hand is more sophisticated since it applies a brh orthology prediction strategy.
specifically, hamstr uses profile hidden markov models  that represent properties of the aligned amino acid sequences of each known og to search a transcript library on the amino acid level for matches.
all retrieved hits are then searched against the entire set of proteins, i.e., the proteome  as reference gene set , of each of the species of which amino acid sequences were used to construct the phmm.
if this reciprocal search retrieves the same amino acid sequence that was  used in the construction of the phmm, a the respective transcript is mapped to the og in question.
the algorithm of hamstr is “memoryless”, meaning that during evaluation of the brh criterion for a given og, it does not consider which transcripts have been assigned to other ogs.
since transcripts are assigned to ogs on a per-og basis without considering results from evaluations for other ogs and keeping track of what transcripts have already been assigned, it is possible that a given transcript is mapped to more than one gene.
this issue of redundant transcript assignments can result in a misled inference of phylogenetic relationships, as has been shown  <cit> , and can potentially compromise downstream analyses.
in hamstr, it would be conceivable to prevent redundant transcript assignment by implementing a record of previously assigned transcripts.
however, such a first-come-first-serve approach cannot be justified: transcripts must be assigned to the og that they are most likely orthologous to, not to the og that came first in the search order.
since this serious issue cannot be solved using the hamstr algorithm, we developed orthograph: a different algorithm that circumvents redundant transcript assignments and instead maps transcripts to the globally best matching og.
to assess the sensitivity and accuracy of orthograph, we tested whether or not orthograph a) reliably identifies orthologs, b) detects known paralogs, and c) finds known isoforms or alternative transcripts.
we additionally searched  <dig> de novo-sequenced transcript libraries of apoid wasps for  <dig> orthologous genes to assess the computational performance of orthograph.
finally, we verified that orthograph does not map transcripts to more than one gene by re-analyzing a dataset that has been processed with hamstr.
our results demonstrate that orthograph’s performance is on par with hamstr’s while not suffering from redundant transcript assignment.
further, we emphasize the flexibility of orthograph and highlight features that are likely of particular interest for a wide array of analyses in molecular evolutionary biology and in comparative genomics in particular.
implementation
the orthograph software package is divided into three main tools that handle  database management ,  forward and reverse searches , and  clustering of orthologous transcripts and output .
the separation into three distinct tools is a deliberate design choice to address work environments where users do not have full administrative privileges.
this facilitates implementation in a high-performance computing cluster setup where the administrator can use the appropriate tool to manage the database, while users only need to run the actual analysis tools.
in addition, this design allows the user to evaluate the alignment search results using different settings  quickly without re-running the computationally expensive searches.
orthograph builds on the transcript orthology assessment strategy via brh suggested by  <cit> .
in contrast to the implementation of this strategy in hamstr, orthograph assigns a given transcript to the globally best matching ogs while making sure that no transcript is assigned more than once.
it additionally identifies all transcripts  present in an assembled transcript library that are putatively homologous to a given og.
the specific transcript orthology assignment algorithm is as follows ; note that steps  <dig> through  <dig> are only required once since their output can be used for all subsequent analyses:
the proteomes  of reference species are used as input.
orthologous genes from all reference proteomes are clustered to form orthologous groups .
this information is provided from public databases or one’s own orthology delineation in the rgs.
for each og, the amino acid sequences are aligned and the multiple sequence alignment  is used to construct a profile hmm.
these phmms are used to search the transcript sequences on the amino acid level for candidate homologs.
search results are stored in a relational database.
for each phmm search hit, the target amino acid sequence section matching the phmm is used as a query to search in a database that includes all genes from the rgs  on the amino acid level.
the results of the reverse search are also stored in the relational database.
after all forward and reverse searches have completed, the clustering of brh pairs takes place: search results from all forward searches are sorted by descending alignment bit score.
for each forward alignment search result, the corresponding reverse alignment search results are sorted by descending alignment bit score as well.
they are evaluated in order of descending alignment bit score for the forward search results, starting with the highest alignment bit score.
if the best reverse search hit of a given transcript is part of the og that the phmm for the forward search is based on , the target transcript is assigned to the og.
the target transcript section is marked so that it cannot be assigned again.
each entry in the database is evaluated in this manner.
fig.
<dig> orthograph workflow.
from a set of reference proteins , the proteins are clustered to form orthologous groups  .
these ogs are aligned to construct profile hidden markov models  .
the phmms are used to search for candidate orthologs in the target library .
each of the obtained hit amino acid sequences  is used as a query for a blast search in a database comprising all reference proteins  .
search results from both forward and reverse searches  are collated and sorted by bit score, with the reverse search result order being subordinated to the forward result order .
this list is evaluated in descending order: if the reverse search hit a protein that is part of the og used for the forward search, the candidate ortholog is mapped to the og
orthograph performs several post-processing steps on transcripts assigned to ogs.
by aligning the transcript fulfilling the brh criterion to the most similar orthologous amino acid sequence of a reference species using exonerate  <cit> , it infers a frameshift-corrected open reading frame .
orthograph allows to extend the orf beyond the phmm alignment sequence section for which the brh criterion was fulfilled while making sure that the orthologous region is covered by a user-defined percentage of the orf length.
subsequently, it provides both the amino acid sequence and the exactly corresponding frameshift-corrected nucleotide sequence of a given transcript.
additionally, orthograph can concatenate transcripts of a given og to simplify downstream analyses .
in all above analysis steps, the user can fine-tune all relevant search and evaluation parameters using configuration files for clarity, documentation, and reproducibility.
orthograph has been developed with user friendliness in mind.
as a result, it is easy to install and runs on any unix/linux system  that provides its dependencies .
the generation of custom-tailored ortholog sets, e.g., from public databases is facilitated by its ability to parse simple tab-delimited tables.
input from public databases such as orthodb is easily formatted accordingly using standard unix or spreadsheet tools.
in addition, the orthograph package contains helper scripts that simplify the preparation of rgs sequence files for custom-made ortholog sets as well as summarize results for multiple analyses, e.g., different species or using different settings.
when designing a custom ortholog set, users should pay close attention to the taxon sampling.
genes that occur in at least two species in each og are recommended so that the resulting phmms are more informative than when based on single sequences only.
in terms of og number, there is no lower or upper bound since the selection depends on the research question.
orthograph runtime increases linearly with each additional og.
detailed methods, data sources as well as system requirements are listed in the additional file  <dig> .
RESULTS
sensitivity and accuracy when searching for single-copy orthologs
to assess the sensitivity and accuracy of orthograph, we employed it to identify genes of known orthology in the rgs of the honeybee, apis mellifera , and jerdon’s jumping ant, harpegnathos saltator .
specifically, we searched the rgs for  <dig> protein-coding genes provided by orthodb  <dig>  <cit>  as being single-copy across four species of hymenoptera  and the outgroup beetle tribolium castaneum  <cit>  .
note that we removed all entries of the respective taxon whose rgs we analyzed for assessing the sensitivity and accuracy of orthograph from this ortholog set .
of the  <dig> protein-coding genes that we searched for, orthograph identified  <dig>  in the rgs of a. mellifera and  <dig>  in the rgs of h. saltator .
in the case of a. mellifera, five proteins were assigned to other ogs than they were assigned by orthodb.
we found a similar result for three proteins of the rgs of h. saltator.
visual inspection of these proteins suggested that the orthology assignment of these proteins in the orthodb database is not correct .
the low fraction  of non-recalled genes were caused by a comparable effect .
thus, the sensitivity , defined as the ratio of true positives to true positives plus false negatives, was  <dig>  for the a. mellifera rgs and  <dig>  for the h. saltator rgs.
the accuracy, defined as the ratio of true positives plus true negatives to the total number of genes in the rgs, was  <dig>  for the a. mellifera rgs and  <dig>  for the h. saltator rgs.
a. mellifera
h. saltator
a. mellifera
h. saltator
c. floridanus
c. floridanus
a. cephalotes
sensitivity is defined as the ratio of true positives  to tp plus false negatives .
accuracy is defined as the ratio of tp plus true negatives  to the total number of genes in the official gene set .
fp, false positives.
note that the results are meant to demonstrate equality in performance despite algorithmic differences
for comparison, hamstr v <dig> .
<dig> was run on the same datasets with comparable parameters.
hamstr identified  <dig> genes  in the rgs of a. mellifera  and  <dig> genes  in the rgs of h. saltator .
this results in a sensitivity of  <dig>  in the a. mellifera rgs and of  <dig>  in the h. saltator rgs, and an accuracy of  <dig>  in the a. mellifera rgs and of  <dig>  in the h. saltator rgs.
the input data on ortholog relations were retrieved from orthodb which contains og information inferred in a purely automated fashion  <cit> .
orthodb has been attested low numbers of false positives and spurious assignments  <cit> ; the proportion of less than 1% of the genes that were recalled wrongly by orthograph are in line with these benchmarks.
orthograph and hamstr perform roughly equally in accuracy and sensitivity when it comes to identifying single-copy orthologs.
identification of splice variants or isoforms
we used orthograph to assess orthologous amino acid sequences including isoforms in the rgs of the florida carpenter ant, camponotus floridanus, a species whose genes and corresponding proteins are part of the ortholog set analyzed before .
in the c. floridanus rgs, eight genes that are part of the ortholog set each encode an alternative isoform.
orthograph readily assigned the alternative isoforms of seven of these genes to the correct ogs.
in the remaining gene, however, the amino acid sequence of the isoform that orthograph could not find was very short  in length.
only  <dig> of the  <dig> amino acid sites can be well aligned to the og and were identified as brh.
it is possible that amino acid sequences that are significantly shorter than the majority of the og are scored poorly by the phmm search and/or the subsequent reverse search so that they eventually do not fulfill the brh criterion and are not recognized by orthograph.
hamstr, in comparison, also identified all isoforms of seven of the eight genes correctly.
however, it reports them as co-orthologs.
strictly speaking, this term is only correct when, while searching for single-copy orthologs, one or more copies of the same gene are identified.
orthograph, in addition to reporting, provides tabular output with alignment coordinates, hmm alignment bit scores and e-values for further statistical analyses.
while it would be highly desirable for users to also obtain information on the occurrence of different isoforms  in different species, alternative transcripts are difficult to distinguish from transcripts of inparalogs or from transcript assembly artifacts without additional information, for example on the genealogy of the species, whose transcript libraries have been investigated, and/or on the transcript’s expression level.
however, orthograph provides tabular output files that can facilitate corresponding downstream analyses.
specifically, the orthograph output files inform about a) what transcripts form brhs with ortholog groups and b) what transcripts assigned by orthograph to the same ortholog group overlap  and could thus represent alternative transcripts .
protein isoforms and splice variants in the reference ortholog set can lead to systematic errors and false positives
the presence of isoforms and splice variants in an rgs dataset can lead to wrong clustering to ogs and/or false negatives .
because it is impossible to know in advance which isoform of a gene or transcribed gene is present in a given transcript library, it is likely that a brh search will fail if more than one highly similar amino acid sequence are present in the reference rgss.
this occurs because the best reverse search hit of a candidate ortholog against the database comprising all proteins in an rgs may return an isoform of the protein that was not used in the phmm, leading to a failure to fulfill the brh criterion.
therefore, isoforms should either be removed from rgs databases prior to using them in orthograph , or the ogs should be extended to also include the isoforms.
identification of inparalogs
in order to demonstrate orthograph’s capabilities to detect inparalogous gene copies, we used it to assess genes that are known to have inparalogous copies in the rgs of the leafcutter ant, atta cephalotes  <cit> .
specifically, we retrieved an ortholog set from orthodb  <dig> comprising  <dig> ogs that contain genes that are known to be single copy in the genomes of a. mellifera, c. floridanus, h. saltator, n. vitripennis, and t. castaneum, but are multi-copy genes in a. cephalotes.
these  <dig> ogs include altogether  <dig> single-copy and multi-copy genes from a. cephalotes:  <dig> are duplicated,  <dig> are triplicated, seven have four copies, two have six copies and one has seven copies.
orthograph readily assigned  <dig> of the  <dig> multi-copy genes to the correct og .
two of the  <dig> ogs were not assigned, one of which contained four, the other contained two gene copies.
in both cases, the genes from a. cephalotes were much shorter than the remaining genes in the og , possibly leading to the respective transcripts failing to fulfil the brh criterion in the reverse search step due to an insufficient alignment length.
these edge cases again highlight the importance of high-quality genome sequencing and annotation efforts, as they provide the basis for many downstream analyses, including full-length gene sequences for reference-based orthology assessment.
non-redundant mapping of transcripts
in order to test whether orthograph indeed does not assign transcripts to more than one og, we re-analyzed the dataset published by  <cit> , who used hamstr version  <dig>  <cit> .
orthograph assigned transcripts to  <dig>  ogs, the same number as obtained by  <cit> .
however, orthograph found transcripts of the analyzed genes in, on average, slightly more taxa .
none of the transcripts was assigned to more than one og.
in the dataset published by  <cit> ,  <dig> transcripts were assigned redundantly, however the orthologous regions were not overlapping.
as  <cit>  removed a total of  <dig> % of their sequences from the dataset due to redundantly assigned transcripts, orthograph yielded  <dig> % more taxa per gene, leading to a denser data matrix for downstream  analyses.
computational performance of orthograph
to demonstrate the computational performance of orthograph, we searched  <dig> apoid wasp transcriptome assemblies for  <dig> selected ogs .
the analysis time when using a single thread increases linearly with total transcriptome assembly length .
single-threaded analysis time also increases with the number of assembled transcripts, showing a linear trend, but no significant correlation .
given that next-generation rnaseq datasets tend to be large and current comparative genomic investigations analyze hundreds, if not thousands of genes ), with a linear runtime increase orthograph does not pose a time bottleneck for current and future large-scale studies such as the numerous group-specific subprojects of the 1kite consortium .
for employment in high-performance cluster computing environments, orthograph supports multi-threading: it offers a linear speedup of about 1x until up to four threads .
orthograph scales well with a speedup of  <dig> to 80% per additional thread up to  <dig> threads.
using  <dig> threads reduces orthograph running time to around 11% compared to a single-threaded analysis.
because most of the data are stored in a relational database on the hard drive, orthograph requires only little memory and allows to re-evaluate stored search results with different parameters, which takes only a fraction of the original analysis time.
in a centralized server-client setup using the mysql database backend, the database management overhead is solely handled by the server, freeing cpu resources for the alignment searches on the clients.
for installation in a grid computing environment where adding a dedicated database server is not feasible, the sqlite database backend  <cit>  is provided.
the file-based sqlite database system can be applied anywhere thanks to its portable and performant implementation , thus it is the default database backend in orthograph.
advantages of graph-based orthology prediction strategies
orthograph uses a graph-based approach, like hamstr and orthoselect as well as orthology prediction tools that assess orthology among genes in completely sequenced and annotated genomes, such as orthomcl, orthodb, oma, or inparanoid.
in contrast, tree-based orthology prediction strategies such as treefam, ensembl compara, or the one implemented in  <cit> , employ an algorithm that reconciles a phylogenetic tree topology of a gene or gene set with the topology of the respective species phylogenetic tree.
this requires a) a multiple sequence alignment  of a gene’s amino acid or nucleotide sequences, and b) a phylogenetic tree inference.
both steps are not only computationally expensive, but also introduce additional sources of bias at each step.
the much reduced computational complexity of a bidirectional alignment search compared to a phylogenetic tree inference enables orthograph to run on standard workstation computers without necessitating a high-performance computing environment.
a number of graph-based and tree-based orthology assessment methods have been reviewed by  <cit> .
reference-based orthology search accuracy depends on reference database quality
reference-based algorithms for assessing transcript orthology can only be as accurate as the content of the database providing reference ogs.
the results from testing the performance of orthograph affirm that reference-based orthology prediction requires adequate orthology delineation in reference genomes.
these findings further highlight the necessity for reliable identification of ortholog relations in completely sequenced genomes as well as continuously updated databases such as orthodb that lay the foundation for a plethora of downstream comparative analyses.
in order to provide comprehensive information, these databases require high-quality genomic data as well as reliable structural and functional gene annotation; thus, the importance of continued genome sequencing and rigorous annotation efforts must not be underestimated.
likewise, many assembled  genomes are far from complete in terms of having properly identified their actual gene content  <cit> , which also hinders reliable inference of orthology among them.
reciprocal search by using hmmer and blast
orthograph makes use of both phmm-based and blast search technology.
by combining these two fundamentally different alignment search algorithms, it draws considerable sensitivity and accuracy.
profile hmm-based similarity searches have been shown to be more sensitive than blast when it comes to detecting remotely related sequences  <cit> .
by restricting the reverse blast search to only the sequence that was found to be putatively homologous during the phmm search, the blast query becomes more informative.
therefore, the practice of using blast for the reverse search in orthograph improves confidence in the subsequent orthology hypothesis by applying a conservative search criterion.
for an illustration of the interrelations between the search results and their respective subsequences, see additional file 1: figures s <dig> and s <dig>
blast uses a heuristic algorithm and does not guarantee an optimal local alignment.
to also support a non-heuristic smith-waterman algorithm, we have, in addition to blast, implemented swipe  <cit> , which is also used in orthodb.
swipe uses a blast database, thus the blast package is required to generate the database; however the swipe search algorithm does not result in inconsistencies that are possible with blast’s alignment heuristic.
users can opt to use the swipe algorithm with appropriate configuration settings.
limits of the methods
orthograph is intended to map transcripts of a single species to reference ogs.
orthology or paralogy relations between genes of more than one species cannot be established using transcriptomic datasets as they are inherently incomplete.
for assessing orthology among genes in completely sequenced and annotated genomes, specialized tools exist, such as orthomcl  <cit> , inparanoid  <cit> , or the orthodb toolset, which is now public  <cit> .
additionally, alternative transcripts or splice variants are difficult to distinguish in a de novo transcriptome assembly without additional read coverage data, which is why orthograph refrains from explicitly predicting them.
orthograph does, however, report transcripts that are potential alternative transcripts or splice variants in order to allow researchers to further investigate them.
CONCLUSIONS
with orthograph, we provide a software solution to accurately assign transcripts  to known groups  of orthologous genes .
orthograph maps transcripts to the globally best matching og, circumventing the problem of redundantly assigning transcripts to more than one og.
with its specific algorithm, orthograph solves this issue that earlier implementations of graph-based brh mapping strategies suffered from, while maintaining the high sensitivity and accuracy of the brh approach.
we developed orthograph to be an asset in many fields by offering additional functionality compared to earlier implementations of graph-based brh mapping strategies.
orthograph is easy to install and use and thereby facilitates comparative analyses of transcriptomic and other coding sequence data.
it was furthermore designed to point users to possibly existing alternative transcripts and paralogous genes, thereby significantly broadening the scope of the software.
the wide applicability of orthograph has been demonstrated by its application in a phylogenomic study on apoid wasps using target dna sequencing baits  <cit>  and the numerous subprojects of the international 1kite project, which investigate intraordinal phylogenetic relationships of insects.
orthograph provides researchers with a convenient, performant, general-purpose tool for analyses in a plethora of disciplines in evolutionary biology.
availability and requirements
project name: orthograph;project home page:
https://mptrsen.github.io/orthograph;operating system: linux/os x;programming language: perl, sql;other requirements: see additional file 1: table s <dig>
additional files
additional file  <dig> supplemental methods and data tables.
figure s <dig>  alignment regions in orthograph; figure s <dig>  orf extension criteria; figure s <dig>  orthograph runtime is significantly correlated to total transcriptome assembly length; figure s <dig>  speedup plot for multi-threaded analysis; figure s <dig>  example multiple sequence alignment of an og to demonstrate a possible assignment of a transcript to the “wrong” og.
additional file  <dig> species, 1kite library ids , number of assembled transcripts, total assembly size, n <dig> values, and ncbi genbank accession numbers.
note that the assemblies were filtered to contain only contigs longer than  <dig> bp.
abbreviations
brhbest reciprocal hit
msamultiple sequence alignment
ogortholog group
orfopen reading frame
phmmprofile hidden markov model
rgsreference gene set

 inferring the evolution of gene families, the phylogeny of species, and tracing the biogeography of populations depend on reliable delineation of orthologous genes and paralogous copies of them. while delineation and identification of orthologous and paralogous genes has been firmly established for studying genomic data, few approaches are currently available for assessing transcripts in the same manner. each of these approaches exhibits, and suffers from, specific problems, potentially leading to erroneous species and gene tree inference. we developed a novel software pipeline, called orthograph, for convenient, fast, and reliable identification of orthologous nucleotide or amino acid sequences, which resolves existing algorithmic and software-technical issues. orthograph builds on previously proposed graph-based clustering algorithms, but extends them without sacrificing accuracy or computational speed. when comparing the gene repertoires of species, one of the first analytical steps is the delineation of orthologous genes, i.e., the identification of genes that originated from a single gene in the last common ancestor of the compared species. each of the delineated orthologous groups can also include species- or lineage-specific gene copies, that evolved by gene duplication after the evolutionary split of the ancestor into different species. finally, horizontal gene transfer can give rise to xenologous gene copies from a single ancestral gene. two fundamentally different approaches to identify potential orthologs, paralogs, and xenologs have been established: tree-based and graph-based approaches. the benefit of graph-based approaches, which we will subsequently focus on, is their computational efficiency and scalability. in general, graph-based approaches assessing gene orthology make use of the genome-wide best reciprocal hit criterion. it rests on the assumption that orthologs in two genomes are more similar to each other than to any other gene in the compared genomes, since they are direct and exclusive descendants from a single ancestral gene. various graph-based approaches based on the brh criterion have been developed that de novo infer orthology among genes and proteins in the gene or protein sets of sequenced and annotated organisms, such as orthomcl, coco-cl, orthodb, inparanoid, orthofinder, and oma. the reliability of these methods critically depend on the fact that differential gene loss is the exception and that gene or protein repertoires are complete. this means that in order to apply a graph-based approach to infer gene orthology among genomes, the organisms’ gene or protein repertoire must be reliably known. these methods are therefore not appropriate for assessing orthology among nucleotide sequences in sequenced transcriptomes, since transcript libraries contain only a subset of the organisms’ actual gene repertoire. the nucleotide sequence of a gene may be missing in a given transcript library simply because the gene was not expressed at the time of rna preservation. given that transcriptome sequencing represents an extremely valuable and cost-efficient strategy to sample coding nucleotide sequences of a large fraction of an organism’s gene repertoire, several graph-based approaches have been developed that are dedicated to ortholog identification in transcript libraries. a possible solution to the aforementioned problem in transcript orthology assessment is to assign transcripts to ogs whose genealogical relationships have already been reliably inferred, rather than to infer orthology of these genes de novo from the transcripts. knowledge of the genealogical relationships of genes can be derived from comparative genomic analyses and may be retrievable from public databases such as orthodb. this approach has been implemented in orthoselect and hamstr. however, orthoselect does not implement the brh criterion, but a unidirectional search. orthoselect is thus prone to false positives. hamstr, on the other hand is more sophisticated since it applies a brh orthology prediction strategy. specifically, hamstr uses profile hidden markov models that represent properties of the aligned amino acid sequences of each known og to search a transcript library on the amino acid level for matches. all retrieved hits are then searched against the entire set of proteins, i.e., the proteome as reference gene set, of each of the species of which amino acid sequences were used to construct the phmm. if this reciprocal search retrieves the same amino acid sequence that was used in the construction of the phmm, a the respective transcript is mapped to the og in question. the algorithm of hamstr is “memoryless”, meaning that during evaluation of the brh criterion for a given og, it does not consider which transcripts have been assigned to other ogs. since transcripts are assigned to ogs on a per-og basis without considering results from evaluations for other ogs and keeping track of what transcripts have already been assigned, it is possible that a given transcript is mapped to more than one gene. this issue of redundant transcript assignments can result in a misled inference of phylogenetic relationships, as has been shown, and can potentially compromise downstream analyses. in hamstr, it would be conceivable to prevent redundant transcript assignment by implementing a record of previously assigned transcripts. however, such a first-come-first-serve approach cannot be justified: transcripts must be assigned to the og that they are most likely orthologous to, not to the og that came first in the search order. since this serious issue cannot be solved using the hamstr algorithm, we developed orthograph: a different algorithm that circumvents redundant transcript assignments and instead maps transcripts to the globally best matching og. to assess the sensitivity and accuracy of orthograph, we tested whether or not orthograph a) reliably identifies orthologs, b) detects known paralogs, and c) finds known isoforms or alternative transcripts. we additionally searched de novo-sequenced transcript libraries of apoid wasps for orthologous genes to assess the computational performance of orthograph. finally, we verified that orthograph does not map transcripts to more than one gene by re-analyzing a dataset that has been processed with hamstr. our results demonstrate that orthograph’s performance is on par with hamstr’s while not suffering from redundant transcript assignment. further, we emphasize the flexibility of orthograph and highlight features that are likely of particular interest for a wide array of analyses in molecular evolutionary biology and in comparative genomics in particular. implementation the orthograph software package is divided into three main tools that handle database management, forward and reverse searches, and clustering of orthologous transcripts and output. the separation into three distinct tools is a deliberate design choice to address work environments where users do not have full administrative privileges. this facilitates implementation in a high-performance computing cluster setup where the administrator can use the appropriate tool to manage the database, while users only need to run the actual analysis tools. in addition, this design allows the user to evaluate the alignment search results using different settings quickly without re-running the computationally expensive searches. orthograph builds on the transcript orthology assessment strategy via brh suggested by. in contrast to the implementation of this strategy in hamstr, orthograph assigns a given transcript to the globally best matching ogs while making sure that no transcript is assigned more than once. it additionally identifies all transcripts present in an assembled transcript library that are putatively homologous to a given og. the specific transcript orthology assignment algorithm is as follows; note that steps through are only required once since their output can be used for all subsequent analyses: the proteomes of reference species are used as input. orthologous genes from all reference proteomes are clustered to form orthologous groups. this information is provided from public databases or one’s own orthology delineation in the rgs. for each og, the amino acid sequences are aligned and the multiple sequence alignment is used to construct a profile hmm. these phmms are used to search the transcript sequences on the amino acid level for candidate homologs. search results are stored in a relational database. for each phmm search hit, the target amino acid sequence section matching the phmm is used as a query to search in a database that includes all genes from the rgs on the amino acid level. the results of the reverse search are also stored in the relational database. after all forward and reverse searches have completed, the clustering of brh pairs takes place: search results from all forward searches are sorted by descending alignment bit score. for each forward alignment search result, the corresponding reverse alignment search results are sorted by descending alignment bit score as well. they are evaluated in order of descending alignment bit score for the forward search results, starting with the highest alignment bit score. if the best reverse search hit of a given transcript is part of the og that the phmm for the forward search is based on, the target transcript is assigned to the og. the target transcript section is marked so that it cannot be assigned again. each entry in the database is evaluated in this manner. fig. orthograph workflow. from a set of reference proteins, the proteins are clustered to form orthologous groups. these ogs are aligned to construct profile hidden markov models. the phmms are used to search for candidate orthologs in the target library. each of the obtained hit amino acid sequences is used as a query for a blast search in a database comprising all reference proteins. search results from both forward and reverse searches are collated and sorted by bit score, with the reverse search result order being subordinated to the forward result order. this list is evaluated in descending order: if the reverse search hit a protein that is part of the og used for the forward search, the candidate ortholog is mapped to the og orthograph performs several post-processing steps on transcripts assigned to ogs. by aligning the transcript fulfilling the brh criterion to the most similar orthologous amino acid sequence of a reference species using exonerate, it infers a frameshift-corrected open reading frame. orthograph allows to extend the orf beyond the phmm alignment sequence section for which the brh criterion was fulfilled while making sure that the orthologous region is covered by a user-defined percentage of the orf length. subsequently, it provides both the amino acid sequence and the exactly corresponding frameshift-corrected nucleotide sequence of a given transcript. additionally, orthograph can concatenate transcripts of a given og to simplify downstream analyses. in all above analysis steps, the user can fine-tune all relevant search and evaluation parameters using configuration files for clarity, documentation, and reproducibility. orthograph has been developed with user friendliness in mind. as a result, it is easy to install and runs on any unix/linux system that provides its dependencies. the generation of custom-tailored ortholog sets, e.g., from public databases is facilitated by its ability to parse simple tab-delimited tables. input from public databases such as orthodb is easily formatted accordingly using standard unix or spreadsheet tools. in addition, the orthograph package contains helper scripts that simplify the preparation of rgs sequence files for custom-made ortholog sets as well as summarize results for multiple analyses, e.g., different species or using different settings. when designing a custom ortholog set, users should pay close attention to the taxon sampling. genes that occur in at least two species in each og are recommended so that the resulting phmms are more informative than when based on single sequences only. in terms of og number, there is no lower or upper bound since the selection depends on the research question. orthograph runtime increases linearly with each additional og. detailed methods, data sources as well as system requirements are listed in the additional file.  sensitivity and accuracy when searching for single-copy orthologs to assess the sensitivity and accuracy of orthograph, we employed it to identify genes of known orthology in the rgs of the honeybee, apis mellifera, and jerdon’s jumping ant, harpegnathos saltator. specifically, we searched the rgs for protein-coding genes provided by orthodb as being single-copy across four species of hymenoptera and the outgroup beetle tribolium castaneum. note that we removed all entries of the respective taxon whose rgs we analyzed for assessing the sensitivity and accuracy of orthograph from this ortholog set. of the protein-coding genes that we searched for, orthograph identified in the rgs of a. mellifera and in the rgs of h. saltator. in the case of a. mellifera, five proteins were assigned to other ogs than they were assigned by orthodb. we found a similar result for three proteins of the rgs of h. saltator. visual inspection of these proteins suggested that the orthology assignment of these proteins in the orthodb database is not correct. the low fraction of non-recalled genes were caused by a comparable effect. thus, the sensitivity, defined as the ratio of true positives to true positives plus false negatives, was for the a. mellifera rgs and for the h. saltator rgs. the accuracy, defined as the ratio of true positives plus true negatives to the total number of genes in the rgs, was for the a. mellifera rgs and for the h. saltator rgs. a. mellifera h. saltator a. mellifera h. saltator c. floridanus c. floridanus a. cephalotes sensitivity is defined as the ratio of true positives to tp plus false negatives. accuracy is defined as the ratio of tp plus true negatives to the total number of genes in the official gene set. fp, false positives. note that the results are meant to demonstrate equality in performance despite algorithmic differences for comparison, hamstr v. was run on the same datasets with comparable parameters. hamstr identified genes in the rgs of a. mellifera and genes in the rgs of h. saltator. this results in a sensitivity of in the a. mellifera rgs and of in the h. saltator rgs, and an accuracy of in the a. mellifera rgs and of in the h. saltator rgs. the input data on ortholog relations were retrieved from orthodb which contains og information inferred in a purely automated fashion. orthodb has been attested low numbers of false positives and spurious assignments; the proportion of less than 1% of the genes that were recalled wrongly by orthograph are in line with these benchmarks. orthograph and hamstr perform roughly equally in accuracy and sensitivity when it comes to identifying single-copy orthologs. identification of splice variants or isoforms we used orthograph to assess orthologous amino acid sequences including isoforms in the rgs of the florida carpenter ant, camponotus floridanus, a species whose genes and corresponding proteins are part of the ortholog set analyzed before. in the c. floridanus rgs, eight genes that are part of the ortholog set each encode an alternative isoform. orthograph readily assigned the alternative isoforms of seven of these genes to the correct ogs. in the remaining gene, however, the amino acid sequence of the isoform that orthograph could not find was very short in length. only of the amino acid sites can be well aligned to the og and were identified as brh. it is possible that amino acid sequences that are significantly shorter than the majority of the og are scored poorly by the phmm search and/or the subsequent reverse search so that they eventually do not fulfill the brh criterion and are not recognized by orthograph. hamstr, in comparison, also identified all isoforms of seven of the eight genes correctly. however, it reports them as co-orthologs. strictly speaking, this term is only correct when, while searching for single-copy orthologs, one or more copies of the same gene are identified. orthograph, in addition to reporting, provides tabular output with alignment coordinates, hmm alignment bit scores and e-values for further statistical analyses. while it would be highly desirable for users to also obtain information on the occurrence of different isoforms in different species, alternative transcripts are difficult to distinguish from transcripts of inparalogs or from transcript assembly artifacts without additional information, for example on the genealogy of the species, whose transcript libraries have been investigated, and/or on the transcript’s expression level. however, orthograph provides tabular output files that can facilitate corresponding downstream analyses. specifically, the orthograph output files inform about a) what transcripts form brhs with ortholog groups and b) what transcripts assigned by orthograph to the same ortholog group overlap and could thus represent alternative transcripts. protein isoforms and splice variants in the reference ortholog set can lead to systematic errors and false positives the presence of isoforms and splice variants in an rgs dataset can lead to wrong clustering to ogs and/or false negatives. because it is impossible to know in advance which isoform of a gene or transcribed gene is present in a given transcript library, it is likely that a brh search will fail if more than one highly similar amino acid sequence are present in the reference rgss. this occurs because the best reverse search hit of a candidate ortholog against the database comprising all proteins in an rgs may return an isoform of the protein that was not used in the phmm, leading to a failure to fulfill the brh criterion. therefore, isoforms should either be removed from rgs databases prior to using them in orthograph, or the ogs should be extended to also include the isoforms. identification of inparalogs in order to demonstrate orthograph’s capabilities to detect inparalogous gene copies, we used it to assess genes that are known to have inparalogous copies in the rgs of the leafcutter ant, atta cephalotes. specifically, we retrieved an ortholog set from orthodb comprising ogs that contain genes that are known to be single copy in the genomes of a. mellifera, c. floridanus, h. saltator, n. vitripennis, and t. castaneum, but are multi-copy genes in a. cephalotes. these ogs include altogether single-copy and multi-copy genes from a. cephalotes: are duplicated, are triplicated, seven have four copies, two have six copies and one has seven copies. orthograph readily assigned of the multi-copy genes to the correct og. two of the ogs were not assigned, one of which contained four, the other contained two gene copies. in both cases, the genes from a. cephalotes were much shorter than the remaining genes in the og, possibly leading to the respective transcripts failing to fulfil the brh criterion in the reverse search step due to an insufficient alignment length. these edge cases again highlight the importance of high-quality genome sequencing and annotation efforts, as they provide the basis for many downstream analyses, including full-length gene sequences for reference-based orthology assessment. non-redundant mapping of transcripts in order to test whether orthograph indeed does not assign transcripts to more than one og, we re-analyzed the dataset published by, who used hamstr version. orthograph assigned transcripts to ogs, the same number as obtained by. however, orthograph found transcripts of the analyzed genes in, on average, slightly more taxa. none of the transcripts was assigned to more than one og. in the dataset published by, transcripts were assigned redundantly, however the orthologous regions were not overlapping. as removed a total of % of their sequences from the dataset due to redundantly assigned transcripts, orthograph yielded % more taxa per gene, leading to a denser data matrix for downstream analyses. computational performance of orthograph to demonstrate the computational performance of orthograph, we searched apoid wasp transcriptome assemblies for selected ogs. the analysis time when using a single thread increases linearly with total transcriptome assembly length. single-threaded analysis time also increases with the number of assembled transcripts, showing a linear trend, but no significant correlation. given that next-generation rnaseq datasets tend to be large and current comparative genomic investigations analyze hundreds, if not thousands of genes ), with a linear runtime increase orthograph does not pose a time bottleneck for current and future large-scale studies such as the numerous group-specific subprojects of the 1kite consortium. for employment in high-performance cluster computing environments, orthograph supports multi-threading: it offers a linear speedup of about 1x until up to four threads. orthograph scales well with a speedup of to 80% per additional thread up to threads. using threads reduces orthograph running time to around 11% compared to a single-threaded analysis. because most of the data are stored in a relational database on the hard drive, orthograph requires only little memory and allows to re-evaluate stored search results with different parameters, which takes only a fraction of the original analysis time. in a centralized server-client setup using the mysql database backend, the database management overhead is solely handled by the server, freeing cpu resources for the alignment searches on the clients. for installation in a grid computing environment where adding a dedicated database server is not feasible, the sqlite database backend is provided. the file-based sqlite database system can be applied anywhere thanks to its portable and performant implementation, thus it is the default database backend in orthograph. advantages of graph-based orthology prediction strategies orthograph uses a graph-based approach, like hamstr and orthoselect as well as orthology prediction tools that assess orthology among genes in completely sequenced and annotated genomes, such as orthomcl, orthodb, oma, or inparanoid. in contrast, tree-based orthology prediction strategies such as treefam, ensembl compara, or the one implemented in, employ an algorithm that reconciles a phylogenetic tree topology of a gene or gene set with the topology of the respective species phylogenetic tree. this requires a) a multiple sequence alignment of a gene’s amino acid or nucleotide sequences, and b) a phylogenetic tree inference. both steps are not only computationally expensive, but also introduce additional sources of bias at each step. the much reduced computational complexity of a bidirectional alignment search compared to a phylogenetic tree inference enables orthograph to run on standard workstation computers without necessitating a high-performance computing environment. a number of graph-based and tree-based orthology assessment methods have been reviewed by. reference-based orthology search accuracy depends on reference database quality reference-based algorithms for assessing transcript orthology can only be as accurate as the content of the database providing reference ogs. the results from testing the performance of orthograph affirm that reference-based orthology prediction requires adequate orthology delineation in reference genomes. these findings further highlight the necessity for reliable identification of ortholog relations in completely sequenced genomes as well as continuously updated databases such as orthodb that lay the foundation for a plethora of downstream comparative analyses. in order to provide comprehensive information, these databases require high-quality genomic data as well as reliable structural and functional gene annotation; thus, the importance of continued genome sequencing and rigorous annotation efforts must not be underestimated. likewise, many assembled genomes are far from complete in terms of having properly identified their actual gene content, which also hinders reliable inference of orthology among them. reciprocal search by using hmmer and blast orthograph makes use of both phmm-based and blast search technology. by combining these two fundamentally different alignment search algorithms, it draws considerable sensitivity and accuracy. profile hmm-based similarity searches have been shown to be more sensitive than blast when it comes to detecting remotely related sequences. by restricting the reverse blast search to only the sequence that was found to be putatively homologous during the phmm search, the blast query becomes more informative. therefore, the practice of using blast for the reverse search in orthograph improves confidence in the subsequent orthology hypothesis by applying a conservative search criterion. for an illustration of the interrelations between the search results and their respective subsequences, see additional file 1: figures s and s blast uses a heuristic algorithm and does not guarantee an optimal local alignment. to also support a non-heuristic smith-waterman algorithm, we have, in addition to blast, implemented swipe, which is also used in orthodb. swipe uses a blast database, thus the blast package is required to generate the database; however the swipe search algorithm does not result in inconsistencies that are possible with blast’s alignment heuristic. users can opt to use the swipe algorithm with appropriate configuration settings. limits of the methods orthograph is intended to map transcripts of a single species to reference ogs. orthology or paralogy relations between genes of more than one species cannot be established using transcriptomic datasets as they are inherently incomplete. for assessing orthology among genes in completely sequenced and annotated genomes, specialized tools exist, such as orthomcl, inparanoid, or the orthodb toolset, which is now public. additionally, alternative transcripts or splice variants are difficult to distinguish in a de novo transcriptome assembly without additional read coverage data, which is why orthograph refrains from explicitly predicting them. orthograph does, however, report transcripts that are potential alternative transcripts or splice variants in order to allow researchers to further investigate them.  with orthograph, we provide a software solution to accurately assign transcripts to known groups of orthologous genes. orthograph maps transcripts to the globally best matching og, circumventing the problem of redundantly assigning transcripts to more than one og. with its specific algorithm, orthograph solves this issue that earlier implementations of graph-based brh mapping strategies suffered from, while maintaining the high sensitivity and accuracy of the brh approach. we developed orthograph to be an asset in many fields by offering additional functionality compared to earlier implementations of graph-based brh mapping strategies. orthograph is easy to install and use and thereby facilitates comparative analyses of transcriptomic and other coding sequence data. it was furthermore designed to point users to possibly existing alternative transcripts and paralogous genes, thereby significantly broadening the scope of the software. the wide applicability of orthograph has been demonstrated by its application in a phylogenomic study on apoid wasps using target dna sequencing baits and the numerous subprojects of the international 1kite project, which investigate intraordinal phylogenetic relationships of insects. orthograph provides researchers with a convenient, performant, general-purpose tool for analyses in a plethora of disciplines in evolutionary biology. availability and requirements project name: orthograph;project home page: https://mptrsen.github.io/orthograph;operating system: linux/os x;programming language: perl, sql;other requirements: see additional file 1: table s additional files additional file supplemental methods and data tables. figure s alignment regions in orthograph; figure s orf extension criteria; figure s orthograph runtime is significantly correlated to total transcriptome assembly length; figure s speedup plot for multi-threaded analysis; figure s example multiple sequence alignment of an og to demonstrate a possible assignment of a transcript to the “wrong” og. additional file species, 1kite library ids, number of assembled transcripts, total assembly size, n values, and ncbi genbank accession numbers. note that the assemblies were filtered to contain only contigs longer than bp. abbreviations brhbest reciprocal hit msamultiple sequence alignment ogortholog group orfopen reading frame phmmprofile hidden markov model rgsreference gene set 
we demonstrate the performance of our approach on de novo-sequenced and assembled transcript libraries of species of apoid wasps as well as on published genomic datasets. additionally, we release de novo-sequenced and assembled transcript libraries of apoid wasp species. with orthograph, we implemented a best reciprocal hit approach to reference-based orthology prediction for coding nucleotide sequences such as rnaseq data. orthograph applies a best reciprocal hit search strategy using profile hidden markov models and maps nucleotide sequences to the globally best matching cluster of orthologous genes, thus enabling researchers to conveniently and reliably delineate orthologs and paralogs from transcriptomic and genomic sequence data. here, identification of orthologous nucleotide or amino acid sequences can be achieved using a graph-based approach that maps nucleotide sequences to genes of known orthology. orthologous genes in two organisms can be identified by applying a so-called reciprocal search strategy, given that complete information of the organisms’ gene repertoire is available. orthology characterizes genes of different organisms that arose from a single ancestral gene via speciation, in contrast to paralogy, which is assigned to genes that arose via gene duplication.
 orthology characterizes genes of different organisms that arose from a single ancestral gene via speciation, in contrast to paralogy, which is assigned to genes that arose via gene duplication. an accurate orthology assignment is a crucial step for comparative genomic studies. orthologous genes in two organisms can be identified by applying a so-called reciprocal search strategy, given that complete information of the organisms’ gene repertoire is available. in many investigations, however, only a fraction of the gene content of the organisms under study is examined. here, identification of orthologous nucleotide or amino acid sequences can be achieved using a graph-based approach that maps nucleotide sequences to genes of known orthology. existing implementations of this approach, however, suffer from algorithmic issues that may cause problems in downstream analyses.  we present a new software pipeline, orthograph, that addresses and solves the above problems and implements useful features for a wide range of comparative genomic and transcriptomic analyses. orthograph applies a best reciprocal hit search strategy using profile hidden markov models and maps nucleotide sequences to the globally best matching cluster of orthologous genes, thus enabling researchers to conveniently and reliably delineate orthologs and paralogs from transcriptomic and genomic sequence data. we demonstrate the performance of our approach on de novo-sequenced and assembled transcript libraries of species of apoid wasps as well as on published genomic datasets.  with orthograph, we implemented a best reciprocal hit approach to reference-based orthology prediction for coding nucleotide sequences such as rnaseq data. orthograph is flexible, easy to use, open source and freely available at https://mptrsen.github.io/orthograph. additionally, we release de novo-sequenced and assembled transcript libraries of apoid wasp species. electronic supplementary material the online version of this article contains supplementary material, which is available to authorized users. keywords orthologyparalogysplice variantssphecidaecrabronidaetranscriptomeissue-copyright-statement© the author 2017 