BACKGROUND
phylogenetic inference algorithms have a very long history  <cit> .
the earliest algorithms used information about macroscopic phenotypic "characters" to determine the evolutionary relationships between species.
so it was natural that as soon as genetic  or genetically encoded  sequences became available, these were treated as "molecular characters" that could be used, essentially in an identical manner to phenotypic characters, to elucidate species relationships.
out of this character evolution paradigm were developed techniques such as the maximum parsimony algorithm  <cit> , and various approximate methods that aim toward parsimony such as neighbor-joining   <cit> , as well as methods that assume constant "molecular clock"-like behavior such as the unweighted pair group method with arithmetic mean   <cit> .
more recently, a different paradigm has developed specifically for molecular sequences.
this sequence evolution paradigm is exemplified by maximum likelihood   <cit>  and bayesian  <cit>  methods, which use an explicit model of how molecular sequences change over time.
different possible evolutionary histories  are distinguished by their relative likelihood under a particular model of sequence evolution.
this paradigm has also led to the use of "corrected" distances calculated using a sequence evolution model, as an input into distance-based methods such as nj and upgma.
many of the important recent developments in phylogenetic inference have involved constructing ever more realistic models of sequence evolution.
the increased accuracy has a price, though, both in the computational power required and in the complexity of downstream analysis, such as interpreting the resulting inferences and comparing alternative hypotheses from different models or parameter sets.
in the genomic age, knowledge of a "representative genome" for many different species provides the opportunity to consider yet another paradigm, which we dub the genome evolution paradigm.
recently, several approaches have been developed that make use of genomic information in the construction of gene trees.
one common method is species tree reconciliation  <cit> , which takes a gene tree  and then prunes and rearranges branches  to reduce the number of implied gene duplications and losses given a known species tree.
the soft parsimony algorithm  <cit>  extends tree reconciliation to minimize duplications and losses given an uncertain species tree .
the spidir algorithm  <cit>  extends the sequence evolution paradigm by learning lineage-specific rate parameters for phylogenetic reconstruction over a large number of orthologous gene trees simultaneously.
the synergy algorithm  <cit>  constructs a gene tree by using a known species tree to specify the sequence of iterative steps--bottom-up from leaves to root--of building and rooting nj trees.
in addition to sequence dissimilarity, the distance used in the nj step includes an empirical term to capture synteny, or shared genomic context, which provides long-range  genomic sequence evidence of common descent.
synteny has been used in a number of gene tree inference algorithms  <cit> , and results from the inheritance of contiguous sequence regions that include more than one product-encoding gene.
existing algorithms within the genome evolution paradigm have shown that including this additional information generally improves gene tree inference, but they are algorithmically quite complex and computationally expensive.
we set out to ask the question: given the constraints that can be derived from knowledge of whole genomes, how simple can we make a gene tree inference algorithm?
what is a minimal set of principles underlying the evolution of gene families needed to reliably reconstruct gene histories?
note that the inference of gene trees in the genome evolution paradigm builds upon either the character or sequence evolution paradigms--as described above, sequence data retain a primary role in all such algorithms proposed to date.
the difference is that, in the genome evolution paradigm, we can make use of information from whole genomes in addition to that which can be derived from information inherent in each gene itself.
in giga, we make use of two additional sources of information, which are applicable for even very distant relationships .
first, in the genomic era, we have more accurate knowledge of the "true" species tree .
whole genome sequences have provided important information for resolving many species relationships that were difficult to determine from physical characters, or from sequences of individual genes.
second, the genome sequence provides nearly complete knowledge of the genes in the genome .
this is critically important for distinguishing between alternative hypotheses for gene trees, and for locating gene duplication events relative to speciation events.
however, it is also important to acknowledge the limitations of the genome evolution paradigm for gene trees.
despite much rhetoric to the contrary, these are still early days in the genomic age.
gene predictions are not of uniformly high quality  <cit> , and any inference algorithm must take steps to minimize errors arising from low-quality predictions.
in summary, our approach is to infer phylogenetic trees of gene families using 1) a "known" species tree, 2) knowledge of all recognizable members of a given family in each genome, and 3) identification of potentially problematic gene predictions, together with 4) some knowledge derived from the molecular sequences.
our hypothesis was that the genomic constraints and detection of potentially problematic sequences might allow the use of an extremely rudimentary representation of the sequences themselves.
if so, we could develop a simple algorithm that would be straightforward to interpret and to improve in the future.
we call our algorithm giga , and it differs from existing genome evolution paradigm methods in that it does not, at any point, construct a tree using existing character or sequence evolution methods such as nj or ml.
like the very simple, efficient upgma method, it builds up a gene tree iteratively using a pairwise sequence distance matrix.
however, in stark contrast to upgma, the final tree topology from giga does not simply reflect the order in which sequence pairs are joined during the algorithm.
rather, the algorithm uses simple rules based on knowledge of evolutionary processes, for inferring the tree topology from the order of pairwise operations.
in the following section, we describe these rules and the theoretical and empirical considerations underlying them, in the context of a novel conception of gene trees as being composed of orthologous subtrees  joined together by founding copying events  such as gene duplication and horizontal transfer.
we then describe the giga algorithm in detail.
finally, we assess the algorithm's performance by comparing to a comprehensive set of more than  <dig>  phylogenetic trees from the treefam database.
RESULTS
rationale behind the giga algorithm
in the spirit of making our initial algorithm as simple as possible, we designed a "greedy" algorithm that constructs a tree guided by the sequence distance matrix but additionally applying rules that aim toward a parsimony-like criterion minimizing the number of gene duplication and deletion events  <cit> .
the algorithm iteratively joins together subtrees of sequences, beginning with the two sequences that are closest according to the distance matrix.
the topology of the joined subtree after each iteration is not simply an agglomeration of the constituent subtrees; rather, rules are used to "rearrange" the joined subtree at each iteration, in accordance with additional  knowledge.
in essence, at each stage of the agglomeration process, giga interprets the tree in terms of the evolutionary events  that most likely generated that tree.
we found that, somewhat surprisingly, we needed only a very rudimentary description of sequence distances to build accurate tree topologies.
our initial implementation uses simply the relative pairwise sequence difference: /.
furthermore, unlike other distance-matrix-based methods, our algorithm does not update distances after each step, but uses the "raw" sequence distances throughout .
these additional simplifications are possible because the rules described below strongly constrain the inferred evolutionary history; the sequence distances are required only to represent very approximately any actual sequence divergence from a common ancestor.
orthologous subtrees and gene trees
we first describe a novel conception of gene trees, which will simplify the explanation of our rules for determining the tree topology from the pairwise sequence distance-determined order of operations.
in this conception, a gene tree is composed of "orthologous subtrees", i.e., containing sequences related by speciation events.
each os contains at most one gene from each organism, and every sequence in the subtree is orthologous to the others.
distinct orthologous subtrees are joined together to produce a gene tree, via events that involve the copying  of genetic material to create a new locus within an ancestral genome.
when the copying is from the same genome , the joining event is a gene duplication event; when the copying is from another genome, the joining event is a horizontal transfer event.
in our representation, when a copying event occurs, one copy of the gene "remains" in the same os as its ancestors, while the other copy "founds" a second os.
each os, then, has a "founding copying event", though at the root of the tree this event is unresolved.
thus, each os is defined by 1) a relationship to the os that contains the other duplicated copy , and 2) a date of the fce, relative to speciation events in the sibling os's.
if there has been at least one copying event, there is more than one way to decompose a phylogenetic tree into os's, depending on which copy is chosen to remain in its ancestral subtree, and which is chosen to found a new subtree.
each copying event can be decomposed in n possible ways, where n is the number of descendants of the copying event, so n =  <dig> for a bifurcating event.
thus, for a bifurcating tree with n copying events, there are n <dig> possible decompositions into os's.
figure  <dig> gives an example of a tree with one duplication event  and the two possible ways in which it can be decomposed into os's.
note that this example is designed merely to illustrate our conception that gene trees can be described in terms of os's and the relationships between sibling os's.
the fact that the decomposition is not unique does not bear on our algorithm, as it constructs gene trees from component os's, rather than decomposing a gene tree into constituent os's.
rules for phylogenetic inference
with this representation we can describe rules for phylogenetic inference that can be applied during the distance-based iterative process.
the first three rules describe how the species tree and genome content can be used to determine the topology of each os , distinguish likely speciation from duplication events , and date fces relative to speciation events .
the fourth rule enables initial os's and fces to be revised at later steps in the process.
the fifth rule attempts to minimize errors in tree reconstruction due to sequence fragments .
these rules treat only speciation and gene duplication events, i.e., vertical inheritance of genetic material .
less common, but still important particularly in prokaryotes, is "horizontal" gene transfer, in which dna from a source other than a parent is integrated into the genome.
in this case, the dna being copied originates in another genome.
however, it should be noted that vertical inheritance is generally treated as the null hypothesis even for bacterial genes, and horizontal inheritance is usually established by evidence that rules out vertical inheritance.
we therefore focus in this paper on vertical inheritance, noting that there are already a number of methods for locating horizontal transfer events, such as incongruence with a vertical-only inheritance model  <cit>  including comparison with ancestral sequence reconstructions  <cit> , and extension of maximum parsimony to phylogenetic network representations  <cit> .
rule 1: if a subtree contains only speciation events, the topology is determined by the known species tree
when an ancestral species undergoes a speciation event, it is first separated into two reproductively isolated populations.
within the tree model of gene evolution, this event produces two copies of an ancestral gene, one in each species' genome, and these two copies then proceed to diverge from each other by well-known processes of population genetics, including mutation, random drift, and natural selection.
if only speciation events have occurred, and multiple speciation events do not occur within a relatively short period of time, the gene tree is expected to be congruent with the species tree.
indeed, a major application of gene tree inference has been to infer species relationships.
for genes that approximately obey "molecular clock-like" behavior such as ribosomal rna genes  <cit>  this remains a powerful tool.
however, on a genome-wide scale, the inference of species trees based on single gene trees is notorious for giving different answers for different genes.
while there are evolutionary scenarios, such as incomplete lineage sorting  <cit> , by which a gene tree will be genuinely incongruent with the known species tree, recent studies have concluded that observed incongruence is much more often due to problems with sequence alignment algorithms, tree inference algorithms, and paucity of data when considering only relatively short regions of contiguous sequence, rather than to actual historical causes  <cit> .
particularly relevant to our approach, rasmussen and kellis  <cit>  demonstrated that accounting for lineage-specific rate differences in a bayesian evolutionary model dramatically increased the number of orthologous gene families among drosophila species that matched the gene tree.
two of their important conclusions are that a single gene does not typically contain enough information to adequately resolve gene family relationships, and that lineage-specific differences in evolutionary rate  are a primary cause of incongruence between the species tree and gene tree.
this is not to say that incomplete lineage sorting does not occur, or that a tree is always a good model for gene evolution.
incomplete lineage sorting may lead to cases where a gene tree genuinely disagrees with the known species tree, or agrees over some regions of a gene and not others ; the reason for this disagreement is a breakdown of the gene tree model itself, which treats speciation and duplication as point events occurring to an ancestral genome, rather than as actual population-based events.
rather, these results suggest that for large-scale phylogenetic reconstruction, rate differences and inadequate information within a single gene may pose larger problems than incomplete lineage sorting.
therefore, in giga, we use the known species tree during the tree inference process to define a species tree constraint on the tree topology.
within the gene tree model, the problem of short speciation times can be addressed by simply allowing multifurcations in the underlying species tree.
finally, we note that even incorrect trees that assume the species tree topology is correct are useful as a null hypothesis for establishing that a more complicated evolutionary history has occurred.
rule 2: a duplication event should be inferred only when there is genomic proof that a duplication occurred, viz.
when, during the iterative process, a given subtree contains more than one gene from the same species
as discussed under rule  <dig>  we do not expect phylogenetic inference to be accurate when using information from typical gene-length sequences, and we cannot then expect the agglomerative process, in general, to construct an orthologous tree in the order of the known species relationships.
therefore, when two os's are joined at a given stage of the algorithm, if together they contain only a single gene from each genome, we merge the os's into a single os .
our simple rule assumes that the genes are in fact orthologous, but the sequence data was not adequate for recognizing this relationship.
however, if the os's together contain more than one sequence from any genome, our algorithm retains the two separate os's, which are then joined by a gene duplication event .
this procedure is similar to the "witness of non-orthology" criterion used by dessimoz et al.
<cit>  to identify paralogous relationships in the clusters of orthologous groups  database  <cit> : within-species paralogs  can establish paralogy between pairs of genes  in other species if the distance d>d and d>d.
this criterion is justified by the improbability of overall convergent evolution in molecular sequences.
most molecular sequence evolution is selectively neutral  <cit> , and therefore similarity between molecular sequences is due more to common ancestry than to common selective selective pressures driving sequence convergence.
if x is more similar to z, and y is more similar to z', than x is to y, this is almost certainly due to the fact that x and z have a more recent common ancestor than x and y; and y and z' have a more recent common ancestor than x and y. in other words, the two paralogous genes in genome z, together with pairwise sequence distances, allow us to recognize that x and y are also paralogous.
thus, this is a genome age criterion, and can be used only if we know which genome each of the sequences came from, and if we can assume that our list of genes from each genome is nonredundant.
of course, relatively rare events, such as gene conversion or complementary deletions of paralogs in different genomes, can invalidate this assumption, and further rules could be developed to identify such cases.
rule 3: if two subtrees of orthologous genes are related by a founding copy event, tentatively date the fce using the gene content of the two groups and the known species tree
given a known species tree, if there have been gene duplication events, our task is to determine where each duplication event occurred relative to the speciation events, i.e., which ancestral gene was copied, and when it was copied.
in a character or sequence evolution paradigm, we must infer the location of duplications from sequence divergence.
however, if evolutionary rates differ significantly for different lineages, parsimony and related approaches suffer from artifacts such as "long branch attraction," while likelihood methods typically make assumptions about the evolutionary model such as a constant relative substitution rate at each site.
yet evolutionary rate change is one of the prominent features of gene families, particularly after gene duplication  <cit> .
after a duplication event, at least one copy is free to diverge under relaxed selective constraints and/or positive selection for a new or modified function; in a gene tree model this commonly manifests as branch- or lineage-specific accelerated evolutionary rate that differs among sites.
we propose below that gene duplication events can be located using, in addition to sequence data, gene presence or absence over a particular set of genomes  and knowledge of the species tree.
at the point at which os's are inferred to be related by gene duplication , we have inferred the two descendant sibling lineages of the duplication.
this specifies which sequences arose from a duplication.
because of two constraints--namely, the species tree, and the improbability of convergent sequence evolution--we can also make an initial hypothesis as to when the gene duplication may have occurred.
because, as described above, overall convergent sequence evolution is extremely rare, at the point in the iterative process where two os's  are joined by a duplication event, this duplication event very likely occurred prior to the most recent mrca speciation event in either os.
the most recent common ancestor  speciation event can be determined for each os, from the species tree and the list of species with a gene in the os.
thus, the os must be older than its mrca speciation event.
we can therefore tentatively assign an fce to the os with the more recent mrca speciation event .
if both os's have the same mrca speciation event , both os's can be tentatively assigned an fce.
note that this method of locating the fce is reliable only if we know the full complement of genes in that family, for all the genomes under consideration; otherwise, the inferred founding ancestor for the subtree could depend on missing data rather than established absence of a gene.
note also that gene loss may have occurred within an os, which can cause the mrca speciation event of all the extant sequences in the os to be an underestimate of the age of the founding event .
however, we note that these alternative evolutionary histories become increasingly less likely as we go further back in time, as they invoke an increasing number of independent gene loss events.
thus, in the absence of additional information, the most parsimonious explanation of the data with respect to implied gene deletion events  <cit>  is to connect each pair of related os's according to the most recent fce.
of course, additional information  could be used to revise this estimate, but in our simple algorithm we report only the most parsimonious reconstruction.
this criterion implicitly considers the genomic presence/absence of genes to be a more reliable data source than the molecular sequence evolution rate, as estimated from character or sequence evolution methods.
finally, we note that multiple os's may have the same mrca speciation event and relate to the same sibling os.
in this case, multiple duplications have occurred between the same speciation events, and in this first implementation of giga we allow these to remain unresolved multifurcations.
rule 4: if the founding copy event of an orthologous subtree has already been dated, allow this date to be revised based on additional evidence
gene loss near the fce is not the only reason that the initial mrca speciation event may be an underestimate of the actual age of the fce.
accelerated evolutionary rates near the fce of an os will also result in an underestimate.
however, unlike gene loss , we should be able to recognize most cases of accelerated rates in later iterations of the algorithm, and revise the fce accordingly.
this revision is necessary because we initially date an fce when paralogous sequences are joined .
if a lineage near the true fce is accelerated in evolutionary rate, sequences in this lineage may have diverged more from their orthologs in other species than those orthologs have diverged from genuine paralogs.
as a result, the sequence distances between paralogs will be smaller than those between some ortholog pairs, and the orthologs will be joined at a later iteration than the paralogs.
we can recognize possible cases of accelerated rate near the fce in the following way.
even if there has been an accelerated evolutionary rate, there is likely to be some signal of common ancestry that can identify the diverged sequences as members of the correct orthologous subtree.
we therefore ask whether these diverged sequences are significantly closer to this potentially orthologous subtree than to any other subtree.
consider a stage in the algorithm where the closest remaining pairwise distance asserts that os <dig>  should be merged with os <dig>  into a new os.
if os <dig> contains genuine orthologs, these sequences will most likely retain sequence similarity evidence of this orthology.
recall that the fce of os <dig> was established due to a closer distance  to a sibling os containing at least one paralog of a sequence in os <dig>  thus, if os <dig> is significantly more similar to os <dig> than to the sibling of os <dig> , this would be good evidence that it is actually orthologous to sequences in os <dig>  because we calculate distance as the number of differences per site, we can simply use the jukes-cantor formula to estimate the standard deviation in this distance  <cit> .
depending on the alternative hypothesis to the proposed merge of os <dig> and os <dig>  we take either one or three standard deviations to be significant, and if this criterion is met, the merge proceeds and the fce is revised accordingly.
if the alternative hypothesis is that os <dig> is instead orthologous to the sibling of os <dig> , we require the distance to be closer by at least three standard deviations.
if the alternative hypothesis would require a gene duplication, either of os <dig> or its sibling , then we require less stringent evidence, namely, that the distance be at least one standard deviation closer.
rule 5: if a sequence appears to be a fragment, leave it aside until the tree topology of all non-fragments has been determined
obviously, it is of value to determine the evolutionary histories of as many genes as possible.
however, it is well known that a nontrivial fraction of predicted genes in current genomes are partial predictions, which can cause problems for phylogenetic inference.
sequence fragments cannot be treated the same way as full-length sequences--e.g., for calculating pairwise distances or within a sequence evolution model--because different regions of a gene may be under dramatically different selective pressures, and will therefore evolve at very different rates; consequently distances estimated from part of the sequence may not accurately reflect those of the whole gene.
one way to solve this problem is by constructing a multiple sequence alignment, and then restricting analysis to only those sites that are common to all sequences.
however, this reduces the amount of data available for evolutionary inference, which as discussed above is already inadequate even if the entire gene sequence can be used.
it is not trivial, a priori, to distinguish a sequence fragment from a genuine evolutionary event in which a region of sequence has been gained or lost.
for an evolutionary event, of course, we expect congruence with the phylogenetic tree: once a region of sequence is lost or gained in a particular ancestral gene, this gain or loss will be inherited by its descendants.
because, at a given stage in our tree reconstruction process, we have a hypothesis for the evolutionary history, we can make use of this expected congruence to identify potential sequence fragments on-the-fly.
in our simple algorithm, each os is a hypothesis about a group of sequences that descends from a common ancestor by speciation events, and we can expect to a good approximation that these sequences should have inherited most of the sequence sites present in the ancestor.
thus, we implemented the following simple on-the-fly test for potential fragments.
at a particular step in the iterative process, we are considering a possible merge between two os's to form a new os, based on a distance between two sequences.
we want to avoid a merge if one  of the sequences driving it is a sequence fragment, since in that case the merge would be based on unreliable data.
we first approximate the sites likely to be present in the ancestral sequence as those columns of the multiple sequence alignment for which more than 50% of the sequences in the merged os align an amino acid.
we then test each of the two sequences driving the merge to identify each as a potential fragment.
first, if the sequence is already part of an os with at least three other sequences, it is not considered a fragment, since it passed our fragment test during previous steps, demonstrating that there are at least three other  orthologous sequences with similar structure.
if there are less than three other sequences in its os, we gather all sequences from the potentially new, merged os.
if a sequence does not align more than 50% of the expected sites, it is identified as a potential fragment; the merge is not made; and the sequence is removed from the list of sequences to be used during the remainder of the iterative process.
this prevents the fragment from determining the tree topology at any stage of the algorithm.
however, we found that we could often correctly place sequence fragments during a second iterative process after a tree has been initially reconstructed for all non-fragment sequences.
in this second process, each previously removed fragment is joined into the existing tree according to its shortest distance to a non-fragment sequence.
the giga algorithm
the steps of the algorithm are as follows:
<dig>  preprocessing and setup
<dig>  decide on the genomes to be included; construct the "known" species tree for these genomes
<dig>  for each protein family:
<dig> .
<dig> assemble a "complete" set of genes for the given family.
<dig> .
<dig> create a multiple sequence alignment of the genes in the family.
<dig> .
<dig> select homologous sites in the alignment for sequence comparisons.
we "trim" the alignment by removing a site if more than 15% of the weighted sequences are gapped at that site.
sequences are weighted using the procedure of karplus et al.
<cit> .
<dig> .
<dig> represent sequence divergence at homologous sites.
in the spirit of first trying the simplest model, we calculate the distance between each pair of sequences as simply the fraction of sequence differences at selected homologous sites.
<dig>  for each protein family, infer the gene tree topology by iteratively defining orthologous groups, and how those groups are related via gene duplication events.
initialization: each sequence begins in its own os.
<dig> : consider the closest pair of sequences that has not been treated in previous steps, and do one of the following operations with the two os's containing them :
<dig> .
<dig> join the two os's by a duplication event, and locate the event relative to the speciation events in each os .
if the two os's, taken together, have two genes from a single organism, then they will be joined by a duplication event  if either of the following conditions also holds:
<dig> .
<dig> : the founding duplication event has not been previously located for either os.
<dig> .
<dig> : the founding duplication event has been previously located for only os <dig> and not os <dig>  and joining the two os's will not conflict with this location.
in other words, the phylogenetic span of os <dig> must be less than or equal to that of os <dig>  this constraint means that joining the two os's would not require us to revise an earlier hypothesis about when a duplication event occurred.
the founding duplication event is initially estimated so as to minimize the number of implied deletions, i.e.
the fde of the os with the more recent mrca is set to be immediately prior to that mrca .
<dig> .2: merge the two separate os's into a single os .
<dig> .
<dig>  allow the merge only if the sequences are not likely fragments .
if neither sequence is a fragment then the two os's are merged if one of the following conditions holds:
<dig> .
<dig>  the founding duplication event has not been located for either os.
<dig> .
<dig>  the founding duplication event has been located for only os <dig> and not os <dig>  and merging the two os's will not conflict with this location.
in other words, the mrca speciation event of the merged os is the same as for os <dig>  this constraint means that merging the two os's would not require us to revise an earlier hypothesis about when a gene duplication event occurred.
<dig> .
<dig>  the founding duplication event has been located for only os <dig> and not os <dig>  and merging the two os's will conflict with this location, but there is adequate sequence evidence to support the revised location of the duplication event .
we first calculate the standard deviation of the distance between os <dig> and os <dig>  and that of the distance between os <dig> and the sibling of os <dig> .
if os <dig> and the sibling of os <dig> have no species overlap and might be orthologous, we require that
dist1-dist2> <dig>
otherwise, we require a less stringent criterion that
dist1-dist2> <dig>
<dig>  attempt to add fragments back into the tree.
allow each fragment one attempted merge or join event, based on the shortest distance between the fragment and any non-fragment.
<dig>  infer tree branch lengths
we recommend taking the tree topology generated by giga and estimating branch lengths and ancestral sequences using an ml-based procedure, e.g.
paml  <cit> .
however, in the spirit of the simple algorithm, we compute by default an approximate reconstruction of each ancestral sequence , and then compute branch lengths as the sequence difference between adjacent nodes in the tree, including the jukes-cantor correction  <cit> .
<dig>  infer ancestral sequences at each node.
we do this in a simple manner, by recursion beginning at the leaf nodes .
for each non-leaf node, we consider the descendant nodes and its closest outgroup node.
if the sequence of the closest outgroup node has not yet been determined, use its descendants to define the outgroup.
if over half of the descendant nodes align the same amino acid at a given site, it is inferred to be the most likely ancestral amino acid.
if the descendants disagree, and the outgroup agrees with one of them, the outgroup amino acid is inferred to be the most likely ancestral amino acid.
otherwise, the ancestral amino acid is considered to be unknown .
<dig>  calculate branch lengths from node sequences.
we use a simple measure, the fraction of sequence differences between a parent node and a child node.
the jukes-cantor correction is applied to this value.
however, in one respect we want to be very careful, and calculate distances only over a selected subset of sites.
following a duplication event, it is often the case that one of the duplicates continues to conserve the ancestral function more closely, while the other diverges more rapidly.
we can identify the "least diverged" ortholog by tracing the shorter branch.
because of rate heterogeneity among sites, the relative branch lengths are reliable only if they are calculated over the same sites.
therefore in our algorithm, for branches following a duplication event, lengths are calculated using only those sites that are aligned in all the descendant nodes.
implementation
the giga algorithm has been implemented in the c programming language, and the code is available at ftp://ftp.pantherdb.org/.
testing the giga algorithm
three properties of a phylogenetic inference algorithm are important to assess: speed, accuracy and robustness.
speed  should be assessed over a range of conditions to also determine how well a method scales with increasing number of sequences or alignment length.
robustness describes the sensitivity of the tree topology to perturbations such as adding/removing sequences, "resampled" character states , or different parameter settings.
accuracy describes how well the inferred tree matches the actual history of evolutionary events.
of course, for actual gene families, we cannot go back in time and follow the "true" sequence of events, to know it for certain.
in practice, accuracy can potentially be assessed in two ways: comparison against sequence data generated by "forward" evolutionary simulation for a known tree topology, or comparison with "gold standard" phylogenetic reconstructions.
simulated data sets are widely used, but their relevance for assessing gene tree inference algorithms is not established; the ability of an algorithm to correctly infer the underlying tree may be more dependent on how well it matches the particular simulation algorithm than how well it will work on actual gene data.
on the other hand, there are as yet no "gold-standard" sets of diverse gene phylogeny reconstructions based on actual data.
several groups have used congruence with the "known" species tree as a gold-standard measure  <cit> , but because giga uses such congruence as a constraint, this is not an appropriate test .
we suggest that the treefam resource  <cit>  can be used to provide benchmarks for speed, accuracy and at least one type of robustness, namely the effect of adding more sequences  of potentially lower quality.
treefam contains a large, diverse set of protein families.
moreover, most families display substantial sequence divergence, indicating that they do not represent trivial cases for evolutionary reconstruction.
figure  <dig> shows the distribution of average and minimum pairwise sequence identity across treefam protein alignments .
average pairwise identity is approximately normal, with a mean and standard deviation of 52%+-15%, while the minimum pairwise identity mode is less than 20%, and nearly all families  have a minimum pairwise identity less than 50%.
figure 5b shows the distributions of the number of sequences in the treefam families , and the lengths of the protein alignments.
accuracy cannot be assessed directly , but consistency with treefam trees can be easily assessed.
the quality of treefam trees on average has been established using a number of different metrics  <cit> , so we can reasonably expect that an accurate method should produce trees similar to treefam trees in general.
because there is only one possible topology for a tree of two sequences, and only three possible topologies for a bifurcating tree of three sequences, we confined our analyses to  <dig>  treefam families  comprising four or more sequences.
finally, robustness of an algorithm to perturbations such as adding sequences, and variations in sequence quality, can be assessed by comparing trees constructed from the two different treefam alignments, the "clean" and "full" alignments, which differ only in that the full alignments contain additional sequences from partially sequenced genomes.
a perfectly robust method will infer identical trees for the sequences in the "clean" alignment, regardless of whether or not the additional "full" sequences are also included during the tree building process.
algorithm speed
in order to assess algorithm speed and scaling, we selected two sets of families: one with families of the same alignment length , and one with families of the same number of sequences .
in the current implementation, giga scales similarly to other, commonly used methods in terms of dependence on the number of sequences and alignment length , but is over  <dig> times as fast as neighbor joining , and over  <dig> times as fast as the ml methods phyml and treebest.
accuracy of giga trees: consistency with treebest
as a proxy for accuracy, we compared giga trees directly to treefam "clean" trees .
figure 7a shows the robinson-foulds   <cit>  distances  between treefam clean trees, and giga trees inferred using the same alignment.
overall, the trees produced with the two different algorithms are quite similar, with about 13% of the trees being identical and 64% very similar .
to further characterize the magnitude of these rf distances, we constructed both nj and ml trees from the clean alignments using the phyml program  <cit> .
we then compared the trees from all four methods.
while the rf distance distributions for all comparisons are affected by both the number of sequences and the alignment length, giga and treebest trees are the most similar to each other in almost all cases, except for a few of the smaller trees .
on average, giga and treebest produce the most similar trees, along with nj-ml .
the overall nj-ml similarity is expected, since in phyml the ml tree construction process begins with the nj tree, so the comparable giga-treebest similarity is striking.
for all comparisons, the rf distance correlates with the number of sequences when alignment length is constant , though the giga-treebest distance depends much less upon the family size , presumably due to the species tree guidance.
thus, despite a slight absolute decrease in giga-treebest similarity for larger families, this decrease is small relative to all other comparisons.
also for all comparisons, the rf score is negatively correlated with alignment length when the number of sequences is held fixed , though this effect is much less pronounced for the nj-ml comparison  presumably because the nj tree is used in the ml process.
importantly, all of the different methods tend to converge towards each other as the amount of substitution data increases.
this is consistent with the conclusion of rasmussen and kellis  <cit>  that shorter genes often lack sufficient information for accurate evolutionary reconstruction.
finally, because giga joins the closest sequence pair at each step, it is useful to compare it to the upgma method.
on average, the upgma trees  are much less similar to treebest trees , and perhaps surprisingly, are even less similar to giga trees  than to treebest trees.
thus, on real protein family alignments, the tree construction rules in giga tend to predominate over the algorithmic ordering of joining operations, and these rules dramatically improve the match with treebest trees.
although the differences between giga and treebest trees were not very substantial , we explored these differences further.
because treefam trees use the species tree only as a "soft" constraint, we reasoned that some of the disagreement between the two algorithms was simply due to local rearrangements of speciation events, as opposed to more substantive differences in the location of gene duplication events.
we can quantify this disagreement by comparing the sets of ortholog pairs that are inferred from the two trees.
because two genes are inferred to be orthologous if their most recent common ancestor in a gene tree is a speciation event, a local rearrangement involving only speciation events will have no effect on the inferred ortholog pairs.
differences involving duplication events, on the other hand, will affect the inferred ortholog pairs.
we therefore calculated ortholog pairs for all the trees.
we defined the ortholog pair difference as
1-/
because multiple sequence alignment quality is well known to influence phylogenetic reconstruction, we reasoned that some of the remaining discrepancy between treefam and giga trees might be due to poor alignment quality.
we ran predictedsp  <cit>  on all treefam alignments to generate an alignment score .
we found that families for which giga and treefam differed more substantially  had a strong tendency to have poor alignments.
over half  of families with substantially different trees inferred by the two different algorithms  had a predictedsp score of less than  <dig> , while this was true of only 19% of the families with similar trees .
this strongly suggests that poor alignment quality accounts for a substantial fraction of the discrepancies between treebest and giga trees.
poor alignment quality does not account for all the discrepancies.
despite the overall good agreement between predicted orthologs, there are systematic differences between the two tree inference methods.
over the entire set of more than  <dig>  families we compared, 67% of all ortholog pairs inferred by either algorithm are in exact agreement.
however, the disagreements are not randomly distributed between the two algorithms.
giga infers a substantially larger number of ortholog pairs.
of all ortholog pairs inferred by treebest, 96% are also inferred by giga, but of all ortholog pairs inferred by giga, only 69% are also inferred by treebest .
this difference can be largely explained by the fact that the giga algorithm locates duplication events using a genomic parsimony criterion, while treebest also uses an ml sequence evolution model.
giga will tend to locate duplication events as far as possible toward the leaves of the species tree, to minimize the number of implied deletion events.
this, in turn, will enable a larger number of gene pairs to be traced to a common speciation event ancestor, i.e., a larger number of inferred orthologs.
an example is shown in figure  <dig>
robustness of giga trees
as a baseline, we first assessed the robustness of treebest trees, by comparing the treefam "clean" and "full" trees.
if the treebest algorithm were perfectly robust to the addition of sequences, the topology of the treefam full tree would be identical  to the clean tree.
to identify deviations from perfect robustness, we calculated the rf distance between the treebest clean and full trees.
figure  <dig>  shows that treebest is reasonably robust to the additional sequences.
in relatively few cases are the treebest trees for the clean and full alignments identical  but most are very similar .
we note that the treebest algorithm itself is somewhat different for full and clean alignments, as full trees are estimated using only protein sequences, while clean trees can use nucleotide as well as protein sequences.
to test the robustness of giga, we then constructed two separate giga trees for each treefam family, one from the "clean" protein alignment, and one from the "full" alignment.
we then calculated the rf distance between the two giga trees to measure how much the additional "full" sequences changed the topology inferred for the "clean" sequences.
we found that giga is considerably more robust than treebest to the perturbation of adding sequences , with over 85% of the trees being completely unchanged  and 98% changing in rf distance by less than  <dig> .
the robustness of giga is remarkable, and is due largely to the strong constraints provided by the rules described above.
CONCLUSIONS
we described a simple algorithm, giga, for inferring the evolutionary events that have given rise to a particular gene family.
we then demonstrated that this simple algorithm creates trees that are similar overall to those produced by the much more complex and computationally intensive treebest algorithm  <cit> .
we consider this to be evidence of the accuracy of giga, based a on published analysis of treebest trees  <cit> , though of course evolutionary reconstruction is an ongoing research activity.
giga is over  <dig> times faster than "fast" ml methods such as treebest and phyml, and over  <dig> times faster than neighbor joining.
the giga algorithm can be simple precisely because it makes use of constraints on the evolutionary history that have only recently become available, with the advent of whole genome sequencing.
the overall philosophy of the algorithm is that because of potentially dramatic departures from clocklike behavior in many gene families, even a fairly sophisticated treatment of molecular sequences is likely to be less trustworthy overall as a guide for constructing gene trees than is genome-derived information such as a known species tree, and gene content .
the algorithm does rely on sequences to reveal common ancestry , even if the sequences alone may not reliably date that common ancestor.
of course, giga is not the ultimate implementation of this genome evolution paradigm--rather, it is only a simple first step.
the giga algorithm makes use of ideas that have been employed for some time.
giga is similar to tree reconciliation  <cit>  and soft parsimony  <cit> , but rather than first estimating the entire tree and then reconciling it with the species tree, giga reconciles the tree at each step in the algorithm.
unlike soft parsimony, polytomies in the species tree or from rapidly repeated duplication remain unresolved, "simultaneous" events, in the current implementation of giga.
other algorithms have made use of a species tree to guide gene tree reconstruction, notably synergy  <cit>  and treebest  <cit> .
while synergy uses the species tree to determine the order of iterative nj tree building and rooting, giga builds up different "orthologous subtrees"  simultaneously and determines their relationships based on pairwise distances and genome content.
while treebest uses the species tree to count duplications and deletions, which are then treated in an ml framework with weighted probabilities relative to substitution events, giga minimizes the number of duplications and deletions consistent with the os's, which is tantamount to giving these events a very large weight compared to substitutions.
one of the main advantages of the giga algorithm over other methods is its simplicity.
this simplicity makes it particularly amenable to systematic improvement, as it is easy to identify the algorithmic reasons for the tree topology inferred by giga and to propose additional rules if necessary.
in the future, one could develop rules to handle specific evolutionary events in addition to those addressed in this initial implementation, such as whole genome duplication, horizontal transfer, polytomies and even incomplete lineage sorting.
nevertheless, even with only the few rules presented here, the algorithm performs remarkably well for many applications.
as with nearly all computational methods, giga was designed to address certain applications of phylogenetic inference and is not appropriate for all applications.
giga assumes that the "true" species tree is known , and that we have a whole genome and "complete" knowledge of the genes in that genome.
it is therefore applicable only to genomes that have been fully sequenced and annotated with respect to the genes in the families whose histories we wish to infer.
it is obviously not amenable to analysis of gene sequences obtained by environmental sequencing , nor to inference of species phylogenies from gene sequences, nor to inference of incomplete lineage sorting .
nevertheless, the algorithm has many advantages for problems involving large-scale phylogenetic reconstruction, inference of orthologs, and inference of gene function by homology.
it is very fast, enabling reconstruction of the phylogenies of large gene families.
giga may even be appropriate as a starting point for refinement by "fast" maximum-likelihood methods.
finally, giga is remarkably robust to adding sequences.
this property is particularly useful for phylogenomic databases, as it enables ancestral sequences to be referred to by a stable identifier over successive releases as new genomes are sequenced and new genes are annotated in existing genomes.
in turn, the stable reference to ancestral sequences would enable the large-scale annotation of gene function by homology, explicitly tracing the evolution of gene function within a gene family.
the gene ontology reference genomes project is currently undertaking just such an effort, using the trees produced by the giga algorithm  <cit> .
trees produced by giga for  <dig> completed genomes are now available in the panther version  <dig> database  <cit> , which complements other existing phylogenomics resources that employ other tree reconstruction algorithms, such as treefam  <cit>  , phylomedb  <cit>   and genetrees  <cit>  .
list of abbreviations
fce: founding copy event; giga: gene tree inference in the genomic age; ml: maximum likelihood; mrca: most recent common ancestor; nj: neighbor joining; os: orthologous subtree; rf distance: robinson-foulds distance; upgma: unweighted pair group method with arithmetic mean.

 phylogenetic inference algorithms have a very long history. the earliest algorithms used information about macroscopic phenotypic "characters" to determine the evolutionary relationships between species. so it was natural that as soon as genetic or genetically encoded sequences became available, these were treated as "molecular characters" that could be used, essentially in an identical manner to phenotypic characters, to elucidate species relationships. out of this character evolution paradigm were developed techniques such as the maximum parsimony algorithm, and various approximate methods that aim toward parsimony such as neighbor-joining, as well as methods that assume constant "molecular clock"-like behavior such as the unweighted pair group method with arithmetic mean. more recently, a different paradigm has developed specifically for molecular sequences. this sequence evolution paradigm is exemplified by maximum likelihood and bayesian methods, which use an explicit model of how molecular sequences change over time. different possible evolutionary histories are distinguished by their relative likelihood under a particular model of sequence evolution. this paradigm has also led to the use of "corrected" distances calculated using a sequence evolution model, as an input into distance-based methods such as nj and upgma. many of the important recent developments in phylogenetic inference have involved constructing ever more realistic models of sequence evolution. the increased accuracy has a price, though, both in the computational power required and in the complexity of downstream analysis, such as interpreting the resulting inferences and comparing alternative hypotheses from different models or parameter sets. in the genomic age, knowledge of a "representative genome" for many different species provides the opportunity to consider yet another paradigm, which we dub the genome evolution paradigm. recently, several approaches have been developed that make use of genomic information in the construction of gene trees. one common method is species tree reconciliation, which takes a gene tree and then prunes and rearranges branches to reduce the number of implied gene duplications and losses given a known species tree. the soft parsimony algorithm extends tree reconciliation to minimize duplications and losses given an uncertain species tree. the spidir algorithm extends the sequence evolution paradigm by learning lineage-specific rate parameters for phylogenetic reconstruction over a large number of orthologous gene trees simultaneously. the synergy algorithm constructs a gene tree by using a known species tree to specify the sequence of iterative steps--bottom-up from leaves to root--of building and rooting nj trees. in addition to sequence dissimilarity, the distance used in the nj step includes an empirical term to capture synteny, or shared genomic context, which provides long-range genomic sequence evidence of common descent. synteny has been used in a number of gene tree inference algorithms, and results from the inheritance of contiguous sequence regions that include more than one product-encoding gene. existing algorithms within the genome evolution paradigm have shown that including this additional information generally improves gene tree inference, but they are algorithmically quite complex and computationally expensive. we set out to ask the question: given the constraints that can be derived from knowledge of whole genomes, how simple can we make a gene tree inference algorithm? what is a minimal set of principles underlying the evolution of gene families needed to reliably reconstruct gene histories? note that the inference of gene trees in the genome evolution paradigm builds upon either the character or sequence evolution paradigms--as described above, sequence data retain a primary role in all such algorithms proposed to date. the difference is that, in the genome evolution paradigm, we can make use of information from whole genomes in addition to that which can be derived from information inherent in each gene itself. in giga, we make use of two additional sources of information, which are applicable for even very distant relationships. first, in the genomic era, we have more accurate knowledge of the "true" species tree. whole genome sequences have provided important information for resolving many species relationships that were difficult to determine from physical characters, or from sequences of individual genes. second, the genome sequence provides nearly complete knowledge of the genes in the genome. this is critically important for distinguishing between alternative hypotheses for gene trees, and for locating gene duplication events relative to speciation events. however, it is also important to acknowledge the limitations of the genome evolution paradigm for gene trees. despite much rhetoric to the contrary, these are still early days in the genomic age. gene predictions are not of uniformly high quality, and any inference algorithm must take steps to minimize errors arising from low-quality predictions. in summary, our approach is to infer phylogenetic trees of gene families using 1) a "known" species tree, 2) knowledge of all recognizable members of a given family in each genome, and 3) identification of potentially problematic gene predictions, together with 4) some knowledge derived from the molecular sequences. our hypothesis was that the genomic constraints and detection of potentially problematic sequences might allow the use of an extremely rudimentary representation of the sequences themselves. if so, we could develop a simple algorithm that would be straightforward to interpret and to improve in the future. we call our algorithm giga, and it differs from existing genome evolution paradigm methods in that it does not, at any point, construct a tree using existing character or sequence evolution methods such as nj or ml. like the very simple, efficient upgma method, it builds up a gene tree iteratively using a pairwise sequence distance matrix. however, in stark contrast to upgma, the final tree topology from giga does not simply reflect the order in which sequence pairs are joined during the algorithm. rather, the algorithm uses simple rules based on knowledge of evolutionary processes, for inferring the tree topology from the order of pairwise operations. in the following section, we describe these rules and the theoretical and empirical considerations underlying them, in the context of a novel conception of gene trees as being composed of orthologous subtrees joined together by founding copying events such as gene duplication and horizontal transfer. we then describe the giga algorithm in detail. finally, we assess the algorithm's performance by comparing to a comprehensive set of more than phylogenetic trees from the treefam database.  rationale behind the giga algorithm in the spirit of making our initial algorithm as simple as possible, we designed a "greedy" algorithm that constructs a tree guided by the sequence distance matrix but additionally applying rules that aim toward a parsimony-like criterion minimizing the number of gene duplication and deletion events. the algorithm iteratively joins together subtrees of sequences, beginning with the two sequences that are closest according to the distance matrix. the topology of the joined subtree after each iteration is not simply an agglomeration of the constituent subtrees; rather, rules are used to "rearrange" the joined subtree at each iteration, in accordance with additional knowledge. in essence, at each stage of the agglomeration process, giga interprets the tree in terms of the evolutionary events that most likely generated that tree. we found that, somewhat surprisingly, we needed only a very rudimentary description of sequence distances to build accurate tree topologies. our initial implementation uses simply the relative pairwise sequence difference: /. furthermore, unlike other distance-matrix-based methods, our algorithm does not update distances after each step, but uses the "raw" sequence distances throughout. these additional simplifications are possible because the rules described below strongly constrain the inferred evolutionary history; the sequence distances are required only to represent very approximately any actual sequence divergence from a common ancestor. orthologous subtrees and gene trees we first describe a novel conception of gene trees, which will simplify the explanation of our rules for determining the tree topology from the pairwise sequence distance-determined order of operations. in this conception, a gene tree is composed of "orthologous subtrees", i.e., containing sequences related by speciation events. each os contains at most one gene from each organism, and every sequence in the subtree is orthologous to the others. distinct orthologous subtrees are joined together to produce a gene tree, via events that involve the copying of genetic material to create a new locus within an ancestral genome. when the copying is from the same genome, the joining event is a gene duplication event; when the copying is from another genome, the joining event is a horizontal transfer event. in our representation, when a copying event occurs, one copy of the gene "remains" in the same os as its ancestors, while the other copy "founds" a second os. each os, then, has a "founding copying event", though at the root of the tree this event is unresolved. thus, each os is defined by 1) a relationship to the os that contains the other duplicated copy, and 2) a date of the fce, relative to speciation events in the sibling os's. if there has been at least one copying event, there is more than one way to decompose a phylogenetic tree into os's, depending on which copy is chosen to remain in its ancestral subtree, and which is chosen to found a new subtree. each copying event can be decomposed in n possible ways, where n is the number of descendants of the copying event, so n = for a bifurcating event. thus, for a bifurcating tree with n copying events, there are n possible decompositions into os's. figure gives an example of a tree with one duplication event and the two possible ways in which it can be decomposed into os's. note that this example is designed merely to illustrate our conception that gene trees can be described in terms of os's and the relationships between sibling os's. the fact that the decomposition is not unique does not bear on our algorithm, as it constructs gene trees from component os's, rather than decomposing a gene tree into constituent os's. rules for phylogenetic inference with this representation we can describe rules for phylogenetic inference that can be applied during the distance-based iterative process. the first three rules describe how the species tree and genome content can be used to determine the topology of each os, distinguish likely speciation from duplication events, and date fces relative to speciation events. the fourth rule enables initial os's and fces to be revised at later steps in the process. the fifth rule attempts to minimize errors in tree reconstruction due to sequence fragments. these rules treat only speciation and gene duplication events, i.e., vertical inheritance of genetic material. less common, but still important particularly in prokaryotes, is "horizontal" gene transfer, in which dna from a source other than a parent is integrated into the genome. in this case, the dna being copied originates in another genome. however, it should be noted that vertical inheritance is generally treated as the null hypothesis even for bacterial genes, and horizontal inheritance is usually established by evidence that rules out vertical inheritance. we therefore focus in this paper on vertical inheritance, noting that there are already a number of methods for locating horizontal transfer events, such as incongruence with a vertical-only inheritance model including comparison with ancestral sequence reconstructions, and extension of maximum parsimony to phylogenetic network representations. rule 1: if a subtree contains only speciation events, the topology is determined by the known species tree when an ancestral species undergoes a speciation event, it is first separated into two reproductively isolated populations. within the tree model of gene evolution, this event produces two copies of an ancestral gene, one in each species' genome, and these two copies then proceed to diverge from each other by well-known processes of population genetics, including mutation, random drift, and natural selection. if only speciation events have occurred, and multiple speciation events do not occur within a relatively short period of time, the gene tree is expected to be congruent with the species tree. indeed, a major application of gene tree inference has been to infer species relationships. for genes that approximately obey "molecular clock-like" behavior such as ribosomal rna genes this remains a powerful tool. however, on a genome-wide scale, the inference of species trees based on single gene trees is notorious for giving different answers for different genes. while there are evolutionary scenarios, such as incomplete lineage sorting, by which a gene tree will be genuinely incongruent with the known species tree, recent studies have concluded that observed incongruence is much more often due to problems with sequence alignment algorithms, tree inference algorithms, and paucity of data when considering only relatively short regions of contiguous sequence, rather than to actual historical causes. particularly relevant to our approach, rasmussen and kellis demonstrated that accounting for lineage-specific rate differences in a bayesian evolutionary model dramatically increased the number of orthologous gene families among drosophila species that matched the gene tree. two of their important conclusions are that a single gene does not typically contain enough information to adequately resolve gene family relationships, and that lineage-specific differences in evolutionary rate are a primary cause of incongruence between the species tree and gene tree. this is not to say that incomplete lineage sorting does not occur, or that a tree is always a good model for gene evolution. incomplete lineage sorting may lead to cases where a gene tree genuinely disagrees with the known species tree, or agrees over some regions of a gene and not others; the reason for this disagreement is a breakdown of the gene tree model itself, which treats speciation and duplication as point events occurring to an ancestral genome, rather than as actual population-based events. rather, these results suggest that for large-scale phylogenetic reconstruction, rate differences and inadequate information within a single gene may pose larger problems than incomplete lineage sorting. therefore, in giga, we use the known species tree during the tree inference process to define a species tree constraint on the tree topology. within the gene tree model, the problem of short speciation times can be addressed by simply allowing multifurcations in the underlying species tree. finally, we note that even incorrect trees that assume the species tree topology is correct are useful as a null hypothesis for establishing that a more complicated evolutionary history has occurred. rule 2: a duplication event should be inferred only when there is genomic proof that a duplication occurred, viz. when, during the iterative process, a given subtree contains more than one gene from the same species as discussed under rule we do not expect phylogenetic inference to be accurate when using information from typical gene-length sequences, and we cannot then expect the agglomerative process, in general, to construct an orthologous tree in the order of the known species relationships. therefore, when two os's are joined at a given stage of the algorithm, if together they contain only a single gene from each genome, we merge the os's into a single os. our simple rule assumes that the genes are in fact orthologous, but the sequence data was not adequate for recognizing this relationship. however, if the os's together contain more than one sequence from any genome, our algorithm retains the two separate os's, which are then joined by a gene duplication event. this procedure is similar to the "witness of non-orthology" criterion used by dessimoz et al. to identify paralogous relationships in the clusters of orthologous groups database: within-species paralogs can establish paralogy between pairs of genes in other species if the distance d>d and d>d. this criterion is justified by the improbability of overall convergent evolution in molecular sequences. most molecular sequence evolution is selectively neutral, and therefore similarity between molecular sequences is due more to common ancestry than to common selective selective pressures driving sequence convergence. if x is more similar to z, and y is more similar to z', than x is to y, this is almost certainly due to the fact that x and z have a more recent common ancestor than x and y; and y and z' have a more recent common ancestor than x and y. in other words, the two paralogous genes in genome z, together with pairwise sequence distances, allow us to recognize that x and y are also paralogous. thus, this is a genome age criterion, and can be used only if we know which genome each of the sequences came from, and if we can assume that our list of genes from each genome is nonredundant. of course, relatively rare events, such as gene conversion or complementary deletions of paralogs in different genomes, can invalidate this assumption, and further rules could be developed to identify such cases. rule 3: if two subtrees of orthologous genes are related by a founding copy event, tentatively date the fce using the gene content of the two groups and the known species tree given a known species tree, if there have been gene duplication events, our task is to determine where each duplication event occurred relative to the speciation events, i.e., which ancestral gene was copied, and when it was copied. in a character or sequence evolution paradigm, we must infer the location of duplications from sequence divergence. however, if evolutionary rates differ significantly for different lineages, parsimony and related approaches suffer from artifacts such as "long branch attraction," while likelihood methods typically make assumptions about the evolutionary model such as a constant relative substitution rate at each site. yet evolutionary rate change is one of the prominent features of gene families, particularly after gene duplication. after a duplication event, at least one copy is free to diverge under relaxed selective constraints and/or positive selection for a new or modified function; in a gene tree model this commonly manifests as branch- or lineage-specific accelerated evolutionary rate that differs among sites. we propose below that gene duplication events can be located using, in addition to sequence data, gene presence or absence over a particular set of genomes and knowledge of the species tree. at the point at which os's are inferred to be related by gene duplication, we have inferred the two descendant sibling lineages of the duplication. this specifies which sequences arose from a duplication. because of two constraints--namely, the species tree, and the improbability of convergent sequence evolution--we can also make an initial hypothesis as to when the gene duplication may have occurred. because, as described above, overall convergent sequence evolution is extremely rare, at the point in the iterative process where two os's are joined by a duplication event, this duplication event very likely occurred prior to the most recent mrca speciation event in either os. the most recent common ancestor speciation event can be determined for each os, from the species tree and the list of species with a gene in the os. thus, the os must be older than its mrca speciation event. we can therefore tentatively assign an fce to the os with the more recent mrca speciation event. if both os's have the same mrca speciation event, both os's can be tentatively assigned an fce. note that this method of locating the fce is reliable only if we know the full complement of genes in that family, for all the genomes under consideration; otherwise, the inferred founding ancestor for the subtree could depend on missing data rather than established absence of a gene. note also that gene loss may have occurred within an os, which can cause the mrca speciation event of all the extant sequences in the os to be an underestimate of the age of the founding event. however, we note that these alternative evolutionary histories become increasingly less likely as we go further back in time, as they invoke an increasing number of independent gene loss events. thus, in the absence of additional information, the most parsimonious explanation of the data with respect to implied gene deletion events is to connect each pair of related os's according to the most recent fce. of course, additional information could be used to revise this estimate, but in our simple algorithm we report only the most parsimonious reconstruction. this criterion implicitly considers the genomic presence/absence of genes to be a more reliable data source than the molecular sequence evolution rate, as estimated from character or sequence evolution methods. finally, we note that multiple os's may have the same mrca speciation event and relate to the same sibling os. in this case, multiple duplications have occurred between the same speciation events, and in this first implementation of giga we allow these to remain unresolved multifurcations. rule 4: if the founding copy event of an orthologous subtree has already been dated, allow this date to be revised based on additional evidence gene loss near the fce is not the only reason that the initial mrca speciation event may be an underestimate of the actual age of the fce. accelerated evolutionary rates near the fce of an os will also result in an underestimate. however, unlike gene loss, we should be able to recognize most cases of accelerated rates in later iterations of the algorithm, and revise the fce accordingly. this revision is necessary because we initially date an fce when paralogous sequences are joined. if a lineage near the true fce is accelerated in evolutionary rate, sequences in this lineage may have diverged more from their orthologs in other species than those orthologs have diverged from genuine paralogs. as a result, the sequence distances between paralogs will be smaller than those between some ortholog pairs, and the orthologs will be joined at a later iteration than the paralogs. we can recognize possible cases of accelerated rate near the fce in the following way. even if there has been an accelerated evolutionary rate, there is likely to be some signal of common ancestry that can identify the diverged sequences as members of the correct orthologous subtree. we therefore ask whether these diverged sequences are significantly closer to this potentially orthologous subtree than to any other subtree. consider a stage in the algorithm where the closest remaining pairwise distance asserts that os should be merged with os into a new os. if os contains genuine orthologs, these sequences will most likely retain sequence similarity evidence of this orthology. recall that the fce of os was established due to a closer distance to a sibling os containing at least one paralog of a sequence in os thus, if os is significantly more similar to os than to the sibling of os, this would be good evidence that it is actually orthologous to sequences in os because we calculate distance as the number of differences per site, we can simply use the jukes-cantor formula to estimate the standard deviation in this distance. depending on the alternative hypothesis to the proposed merge of os and os we take either one or three standard deviations to be significant, and if this criterion is met, the merge proceeds and the fce is revised accordingly. if the alternative hypothesis is that os is instead orthologous to the sibling of os, we require the distance to be closer by at least three standard deviations. if the alternative hypothesis would require a gene duplication, either of os or its sibling, then we require less stringent evidence, namely, that the distance be at least one standard deviation closer. rule 5: if a sequence appears to be a fragment, leave it aside until the tree topology of all non-fragments has been determined obviously, it is of value to determine the evolutionary histories of as many genes as possible. however, it is well known that a nontrivial fraction of predicted genes in current genomes are partial predictions, which can cause problems for phylogenetic inference. sequence fragments cannot be treated the same way as full-length sequences--e.g., for calculating pairwise distances or within a sequence evolution model--because different regions of a gene may be under dramatically different selective pressures, and will therefore evolve at very different rates; consequently distances estimated from part of the sequence may not accurately reflect those of the whole gene. one way to solve this problem is by constructing a multiple sequence alignment, and then restricting analysis to only those sites that are common to all sequences. however, this reduces the amount of data available for evolutionary inference, which as discussed above is already inadequate even if the entire gene sequence can be used. it is not trivial, a priori, to distinguish a sequence fragment from a genuine evolutionary event in which a region of sequence has been gained or lost. for an evolutionary event, of course, we expect congruence with the phylogenetic tree: once a region of sequence is lost or gained in a particular ancestral gene, this gain or loss will be inherited by its descendants. because, at a given stage in our tree reconstruction process, we have a hypothesis for the evolutionary history, we can make use of this expected congruence to identify potential sequence fragments on-the-fly. in our simple algorithm, each os is a hypothesis about a group of sequences that descends from a common ancestor by speciation events, and we can expect to a good approximation that these sequences should have inherited most of the sequence sites present in the ancestor. thus, we implemented the following simple on-the-fly test for potential fragments. at a particular step in the iterative process, we are considering a possible merge between two os's to form a new os, based on a distance between two sequences. we want to avoid a merge if one of the sequences driving it is a sequence fragment, since in that case the merge would be based on unreliable data. we first approximate the sites likely to be present in the ancestral sequence as those columns of the multiple sequence alignment for which more than 50% of the sequences in the merged os align an amino acid. we then test each of the two sequences driving the merge to identify each as a potential fragment. first, if the sequence is already part of an os with at least three other sequences, it is not considered a fragment, since it passed our fragment test during previous steps, demonstrating that there are at least three other orthologous sequences with similar structure. if there are less than three other sequences in its os, we gather all sequences from the potentially new, merged os. if a sequence does not align more than 50% of the expected sites, it is identified as a potential fragment; the merge is not made; and the sequence is removed from the list of sequences to be used during the remainder of the iterative process. this prevents the fragment from determining the tree topology at any stage of the algorithm. however, we found that we could often correctly place sequence fragments during a second iterative process after a tree has been initially reconstructed for all non-fragment sequences. in this second process, each previously removed fragment is joined into the existing tree according to its shortest distance to a non-fragment sequence. the giga algorithm the steps of the algorithm are as follows: preprocessing and setup decide on the genomes to be included; construct the "known" species tree for these genomes for each protein family:. assemble a "complete" set of genes for the given family.. create a multiple sequence alignment of the genes in the family.. select homologous sites in the alignment for sequence comparisons. we "trim" the alignment by removing a site if more than 15% of the weighted sequences are gapped at that site. sequences are weighted using the procedure of karplus et al... represent sequence divergence at homologous sites. in the spirit of first trying the simplest model, we calculate the distance between each pair of sequences as simply the fraction of sequence differences at selected homologous sites. for each protein family, infer the gene tree topology by iteratively defining orthologous groups, and how those groups are related via gene duplication events. initialization: each sequence begins in its own os.: consider the closest pair of sequences that has not been treated in previous steps, and do one of the following operations with the two os's containing them:. join the two os's by a duplication event, and locate the event relative to the speciation events in each os. if the two os's, taken together, have two genes from a single organism, then they will be joined by a duplication event if either of the following conditions also holds:.: the founding duplication event has not been previously located for either os..: the founding duplication event has been previously located for only os and not os and joining the two os's will not conflict with this location. in other words, the phylogenetic span of os must be less than or equal to that of os this constraint means that joining the two os's would not require us to revise an earlier hypothesis about when a duplication event occurred. the founding duplication event is initially estimated so as to minimize the number of implied deletions, i.e. the fde of the os with the more recent mrca is set to be immediately prior to that mrca..2: merge the two separate os's into a single os.. allow the merge only if the sequences are not likely fragments. if neither sequence is a fragment then the two os's are merged if one of the following conditions holds:. the founding duplication event has not been located for either os.. the founding duplication event has been located for only os and not os and merging the two os's will not conflict with this location. in other words, the mrca speciation event of the merged os is the same as for os this constraint means that merging the two os's would not require us to revise an earlier hypothesis about when a gene duplication event occurred.. the founding duplication event has been located for only os and not os and merging the two os's will conflict with this location, but there is adequate sequence evidence to support the revised location of the duplication event. we first calculate the standard deviation of the distance between os and os and that of the distance between os and the sibling of os. if os and the sibling of os have no species overlap and might be orthologous, we require that dist1-dist2> otherwise, we require a less stringent criterion that dist1-dist2> attempt to add fragments back into the tree. allow each fragment one attempted merge or join event, based on the shortest distance between the fragment and any non-fragment. infer tree branch lengths we recommend taking the tree topology generated by giga and estimating branch lengths and ancestral sequences using an ml-based procedure, e.g. paml. however, in the spirit of the simple algorithm, we compute by default an approximate reconstruction of each ancestral sequence, and then compute branch lengths as the sequence difference between adjacent nodes in the tree, including the jukes-cantor correction. infer ancestral sequences at each node. we do this in a simple manner, by recursion beginning at the leaf nodes. for each non-leaf node, we consider the descendant nodes and its closest outgroup node. if the sequence of the closest outgroup node has not yet been determined, use its descendants to define the outgroup. if over half of the descendant nodes align the same amino acid at a given site, it is inferred to be the most likely ancestral amino acid. if the descendants disagree, and the outgroup agrees with one of them, the outgroup amino acid is inferred to be the most likely ancestral amino acid. otherwise, the ancestral amino acid is considered to be unknown. calculate branch lengths from node sequences. we use a simple measure, the fraction of sequence differences between a parent node and a child node. the jukes-cantor correction is applied to this value. however, in one respect we want to be very careful, and calculate distances only over a selected subset of sites. following a duplication event, it is often the case that one of the duplicates continues to conserve the ancestral function more closely, while the other diverges more rapidly. we can identify the "least diverged" ortholog by tracing the shorter branch. because of rate heterogeneity among sites, the relative branch lengths are reliable only if they are calculated over the same sites. therefore in our algorithm, for branches following a duplication event, lengths are calculated using only those sites that are aligned in all the descendant nodes. implementation the giga algorithm has been implemented in the c programming language, and the code is available at ftp://ftp.pantherdb.org/. testing the giga algorithm three properties of a phylogenetic inference algorithm are important to assess: speed, accuracy and robustness. speed should be assessed over a range of conditions to also determine how well a method scales with increasing number of sequences or alignment length. robustness describes the sensitivity of the tree topology to perturbations such as adding/removing sequences, "resampled" character states, or different parameter settings. accuracy describes how well the inferred tree matches the actual history of evolutionary events. of course, for actual gene families, we cannot go back in time and follow the "true" sequence of events, to know it for certain. in practice, accuracy can potentially be assessed in two ways: comparison against sequence data generated by "forward" evolutionary simulation for a known tree topology, or comparison with "gold standard" phylogenetic reconstructions. simulated data sets are widely used, but their relevance for assessing gene tree inference algorithms is not established; the ability of an algorithm to correctly infer the underlying tree may be more dependent on how well it matches the particular simulation algorithm than how well it will work on actual gene data. on the other hand, there are as yet no "gold-standard" sets of diverse gene phylogeny reconstructions based on actual data. several groups have used congruence with the "known" species tree as a gold-standard measure, but because giga uses such congruence as a constraint, this is not an appropriate test. we suggest that the treefam resource can be used to provide benchmarks for speed, accuracy and at least one type of robustness, namely the effect of adding more sequences of potentially lower quality. treefam contains a large, diverse set of protein families. moreover, most families display substantial sequence divergence, indicating that they do not represent trivial cases for evolutionary reconstruction. figure shows the distribution of average and minimum pairwise sequence identity across treefam protein alignments. average pairwise identity is approximately normal, with a mean and standard deviation of 52%+-15%, while the minimum pairwise identity mode is less than 20%, and nearly all families have a minimum pairwise identity less than 50%. figure 5b shows the distributions of the number of sequences in the treefam families, and the lengths of the protein alignments. accuracy cannot be assessed directly, but consistency with treefam trees can be easily assessed. the quality of treefam trees on average has been established using a number of different metrics, so we can reasonably expect that an accurate method should produce trees similar to treefam trees in general. because there is only one possible topology for a tree of two sequences, and only three possible topologies for a bifurcating tree of three sequences, we confined our analyses to treefam families comprising four or more sequences. finally, robustness of an algorithm to perturbations such as adding sequences, and variations in sequence quality, can be assessed by comparing trees constructed from the two different treefam alignments, the "clean" and "full" alignments, which differ only in that the full alignments contain additional sequences from partially sequenced genomes. a perfectly robust method will infer identical trees for the sequences in the "clean" alignment, regardless of whether or not the additional "full" sequences are also included during the tree building process. algorithm speed in order to assess algorithm speed and scaling, we selected two sets of families: one with families of the same alignment length, and one with families of the same number of sequences. in the current implementation, giga scales similarly to other, commonly used methods in terms of dependence on the number of sequences and alignment length, but is over times as fast as neighbor joining, and over times as fast as the ml methods phyml and treebest. accuracy of giga trees: consistency with treebest as a proxy for accuracy, we compared giga trees directly to treefam "clean" trees. figure 7a shows the robinson-foulds distances between treefam clean trees, and giga trees inferred using the same alignment. overall, the trees produced with the two different algorithms are quite similar, with about 13% of the trees being identical and 64% very similar. to further characterize the magnitude of these rf distances, we constructed both nj and ml trees from the clean alignments using the phyml program. we then compared the trees from all four methods. while the rf distance distributions for all comparisons are affected by both the number of sequences and the alignment length, giga and treebest trees are the most similar to each other in almost all cases, except for a few of the smaller trees. on average, giga and treebest produce the most similar trees, along with nj-ml. the overall nj-ml similarity is expected, since in phyml the ml tree construction process begins with the nj tree, so the comparable giga-treebest similarity is striking. for all comparisons, the rf distance correlates with the number of sequences when alignment length is constant, though the giga-treebest distance depends much less upon the family size, presumably due to the species tree guidance. thus, despite a slight absolute decrease in giga-treebest similarity for larger families, this decrease is small relative to all other comparisons. also for all comparisons, the rf score is negatively correlated with alignment length when the number of sequences is held fixed, though this effect is much less pronounced for the nj-ml comparison presumably because the nj tree is used in the ml process. importantly, all of the different methods tend to converge towards each other as the amount of substitution data increases. this is consistent with the conclusion of rasmussen and kellis that shorter genes often lack sufficient information for accurate evolutionary reconstruction. finally, because giga joins the closest sequence pair at each step, it is useful to compare it to the upgma method. on average, the upgma trees are much less similar to treebest trees, and perhaps surprisingly, are even less similar to giga trees than to treebest trees. thus, on real protein family alignments, the tree construction rules in giga tend to predominate over the algorithmic ordering of joining operations, and these rules dramatically improve the match with treebest trees. although the differences between giga and treebest trees were not very substantial, we explored these differences further. because treefam trees use the species tree only as a "soft" constraint, we reasoned that some of the disagreement between the two algorithms was simply due to local rearrangements of speciation events, as opposed to more substantive differences in the location of gene duplication events. we can quantify this disagreement by comparing the sets of ortholog pairs that are inferred from the two trees. because two genes are inferred to be orthologous if their most recent common ancestor in a gene tree is a speciation event, a local rearrangement involving only speciation events will have no effect on the inferred ortholog pairs. differences involving duplication events, on the other hand, will affect the inferred ortholog pairs. we therefore calculated ortholog pairs for all the trees. we defined the ortholog pair difference as 1-/ because multiple sequence alignment quality is well known to influence phylogenetic reconstruction, we reasoned that some of the remaining discrepancy between treefam and giga trees might be due to poor alignment quality. we ran predictedsp on all treefam alignments to generate an alignment score. we found that families for which giga and treefam differed more substantially had a strong tendency to have poor alignments. over half of families with substantially different trees inferred by the two different algorithms had a predictedsp score of less than, while this was true of only 19% of the families with similar trees. this strongly suggests that poor alignment quality accounts for a substantial fraction of the discrepancies between treebest and giga trees. poor alignment quality does not account for all the discrepancies. despite the overall good agreement between predicted orthologs, there are systematic differences between the two tree inference methods. over the entire set of more than families we compared, 67% of all ortholog pairs inferred by either algorithm are in exact agreement. however, the disagreements are not randomly distributed between the two algorithms. giga infers a substantially larger number of ortholog pairs. of all ortholog pairs inferred by treebest, 96% are also inferred by giga, but of all ortholog pairs inferred by giga, only 69% are also inferred by treebest. this difference can be largely explained by the fact that the giga algorithm locates duplication events using a genomic parsimony criterion, while treebest also uses an ml sequence evolution model. giga will tend to locate duplication events as far as possible toward the leaves of the species tree, to minimize the number of implied deletion events. this, in turn, will enable a larger number of gene pairs to be traced to a common speciation event ancestor, i.e., a larger number of inferred orthologs. an example is shown in figure robustness of giga trees as a baseline, we first assessed the robustness of treebest trees, by comparing the treefam "clean" and "full" trees. if the treebest algorithm were perfectly robust to the addition of sequences, the topology of the treefam full tree would be identical to the clean tree. to identify deviations from perfect robustness, we calculated the rf distance between the treebest clean and full trees. figure shows that treebest is reasonably robust to the additional sequences. in relatively few cases are the treebest trees for the clean and full alignments identical but most are very similar. we note that the treebest algorithm itself is somewhat different for full and clean alignments, as full trees are estimated using only protein sequences, while clean trees can use nucleotide as well as protein sequences. to test the robustness of giga, we then constructed two separate giga trees for each treefam family, one from the "clean" protein alignment, and one from the "full" alignment. we then calculated the rf distance between the two giga trees to measure how much the additional "full" sequences changed the topology inferred for the "clean" sequences. we found that giga is considerably more robust than treebest to the perturbation of adding sequences, with over 85% of the trees being completely unchanged and 98% changing in rf distance by less than. the robustness of giga is remarkable, and is due largely to the strong constraints provided by the rules described above.  we described a simple algorithm, giga, for inferring the evolutionary events that have given rise to a particular gene family. we then demonstrated that this simple algorithm creates trees that are similar overall to those produced by the much more complex and computationally intensive treebest algorithm. we consider this to be evidence of the accuracy of giga, based a on published analysis of treebest trees, though of course evolutionary reconstruction is an ongoing research activity. giga is over times faster than "fast" ml methods such as treebest and phyml, and over times faster than neighbor joining. the giga algorithm can be simple precisely because it makes use of constraints on the evolutionary history that have only recently become available, with the advent of whole genome sequencing. the overall philosophy of the algorithm is that because of potentially dramatic departures from clocklike behavior in many gene families, even a fairly sophisticated treatment of molecular sequences is likely to be less trustworthy overall as a guide for constructing gene trees than is genome-derived information such as a known species tree, and gene content. the algorithm does rely on sequences to reveal common ancestry, even if the sequences alone may not reliably date that common ancestor. of course, giga is not the ultimate implementation of this genome evolution paradigm--rather, it is only a simple first step. the giga algorithm makes use of ideas that have been employed for some time. giga is similar to tree reconciliation and soft parsimony, but rather than first estimating the entire tree and then reconciling it with the species tree, giga reconciles the tree at each step in the algorithm. unlike soft parsimony, polytomies in the species tree or from rapidly repeated duplication remain unresolved, "simultaneous" events, in the current implementation of giga. other algorithms have made use of a species tree to guide gene tree reconstruction, notably synergy and treebest. while synergy uses the species tree to determine the order of iterative nj tree building and rooting, giga builds up different "orthologous subtrees" simultaneously and determines their relationships based on pairwise distances and genome content. while treebest uses the species tree to count duplications and deletions, which are then treated in an ml framework with weighted probabilities relative to substitution events, giga minimizes the number of duplications and deletions consistent with the os's, which is tantamount to giving these events a very large weight compared to substitutions. one of the main advantages of the giga algorithm over other methods is its simplicity. this simplicity makes it particularly amenable to systematic improvement, as it is easy to identify the algorithmic reasons for the tree topology inferred by giga and to propose additional rules if necessary. in the future, one could develop rules to handle specific evolutionary events in addition to those addressed in this initial implementation, such as whole genome duplication, horizontal transfer, polytomies and even incomplete lineage sorting. nevertheless, even with only the few rules presented here, the algorithm performs remarkably well for many applications. as with nearly all computational methods, giga was designed to address certain applications of phylogenetic inference and is not appropriate for all applications. giga assumes that the "true" species tree is known, and that we have a whole genome and "complete" knowledge of the genes in that genome. it is therefore applicable only to genomes that have been fully sequenced and annotated with respect to the genes in the families whose histories we wish to infer. it is obviously not amenable to analysis of gene sequences obtained by environmental sequencing, nor to inference of species phylogenies from gene sequences, nor to inference of incomplete lineage sorting. nevertheless, the algorithm has many advantages for problems involving large-scale phylogenetic reconstruction, inference of orthologs, and inference of gene function by homology. it is very fast, enabling reconstruction of the phylogenies of large gene families. giga may even be appropriate as a starting point for refinement by "fast" maximum-likelihood methods. finally, giga is remarkably robust to adding sequences. this property is particularly useful for phylogenomic databases, as it enables ancestral sequences to be referred to by a stable identifier over successive releases as new genomes are sequenced and new genes are annotated in existing genomes. in turn, the stable reference to ancestral sequences would enable the large-scale annotation of gene function by homology, explicitly tracing the evolution of gene function within a gene family. the gene ontology reference genomes project is currently undertaking just such an effort, using the trees produced by the giga algorithm. trees produced by giga for completed genomes are now available in the panther version database, which complements other existing phylogenomics resources that employ other tree reconstruction algorithms, such as treefam, phylomedb and genetrees. list of abbreviations fce: founding copy event; giga: gene tree inference in the genomic age; ml: maximum likelihood; mrca: most recent common ancestor; nj: neighbor joining; os: orthologous subtree; rf distance: robinson-foulds distance; upgma: unweighted pair group method with arithmetic mean. 
we describe a simple, fast algorithm for inferring gene phylogenies, which makes use of information that was not available prior to the genomic age: namely, a reliable species tree spanning much of the tree of life, and knowledge of the complete complement of genes in a species' genome. the algorithm, called giga, constructs trees agglomeratively from a distance matrix representation of sequences, using simple rules to incorporate this genomic age information. it is exceptionally robust to adding more gene sequences, opening up the possibility of creating stable identifiers for referring to not only extant genes, but also their common ancestors. giga makes use of a novel conceptualization of gene trees as being composed of orthologous subtrees, which are joined by other evolutionary events such as gene duplication or horizontal gene transfer. however, some remaining differences are algorithmic, and can be explained by the fact that giga tends to put a larger emphasis on minimizing gene duplication and deletion events. we compared trees produced by giga to those in the treefam database, and they were very similar in general, with most differences likely due to poor alignment quality. an important innovation in giga is that, at every step in the agglomeration process, the tree is interpreted/reinterpreted in terms of the evolutionary events that created it. yet the most commonly used computational algorithms for reconstructing gene trees can be inaccurate for numerous reasons, both algorithmic and biological. giga is efficient, allowing phylogenetic reconstruction of very large gene families and determination of orthologs on a large scale. additional information beyond gene sequence data has been shown to improve the accuracy of reconstructions, though at great computational cost.
 phylogenetic relationships between genes are not only of theoretical interest: they enable us to learn about human genes through the experimental work on their relatives in numerous model organisms from bacteria to fruit flies and mice. yet the most commonly used computational algorithms for reconstructing gene trees can be inaccurate for numerous reasons, both algorithmic and biological. additional information beyond gene sequence data has been shown to improve the accuracy of reconstructions, though at great computational cost.  we describe a simple, fast algorithm for inferring gene phylogenies, which makes use of information that was not available prior to the genomic age: namely, a reliable species tree spanning much of the tree of life, and knowledge of the complete complement of genes in a species' genome. the algorithm, called giga, constructs trees agglomeratively from a distance matrix representation of sequences, using simple rules to incorporate this genomic age information. giga makes use of a novel conceptualization of gene trees as being composed of orthologous subtrees, which are joined by other evolutionary events such as gene duplication or horizontal gene transfer. an important innovation in giga is that, at every step in the agglomeration process, the tree is interpreted/reinterpreted in terms of the evolutionary events that created it. remarkably, giga performs well even when using a very simple distance metric and no distance averaging over clades during the tree construction process.  giga is efficient, allowing phylogenetic reconstruction of very large gene families and determination of orthologs on a large scale. it is exceptionally robust to adding more gene sequences, opening up the possibility of creating stable identifiers for referring to not only extant genes, but also their common ancestors. we compared trees produced by giga to those in the treefam database, and they were very similar in general, with most differences likely due to poor alignment quality. however, some remaining differences are algorithmic, and can be explained by the fact that giga tends to put a larger emphasis on minimizing gene duplication and deletion events. 