BACKGROUND
motivated by the general need to identify and classify species based on molecular evidence, alignment-free genome comparisons have been proposed, based on comparing chaos game representations  of genomic dna sequences.
the cgr of a dna sequence, proposed by jeffrey  <cit> , is a graphical representation of a dna sequence, where the patterns in the image correspond to the frequencies of k-mers in the sequence.
deschavanne et al.
<cit>  were the first to suggest that cgr is a good candidate for the role of “genomic signature” defined by karlin and burge  <cit>  as any specific quantitative characteristic of a sequence that is pervasive along the genome, while being dissimilar for sequences originating from organisms of different species.
cgr is one of a variety of alignment-free methods  that have been proposed for sequence and genome comparisons, as a computationally efficient approach that performs well even with dna sequences that have nothing or little in common.
, mtdna , cpdna , and pdna ).
initially, cgr images were only qualitatively analyzed , and dutta et al.
and goldman both advanced the suggestion that cgr images represent no more information than second-order markov chains  <cit> , which was later disproven by almeida et al.
<cit>  and others  <cit> .
cgr has been applied extensively to phylogenetics together with the euclidean distance, for instance on ndna fragments from various domains  <cit> ,  <dig> genomes from various genera  <cit> ,  <dig> ndna fragments from several bird genomes  <cit> ,  <dig> mtdna sequences   <cit> ,  <dig> bacteria and about  <dig> phages  <cit> ,  <dig> hiv- <dig> genomes  <cit> ,  <dig> mtdna sequences and  <dig> ndna sequences from plants in the brassicales order  <cit> .
other distances have also been used, for instance the dssim image distance on a set of  <dig>  mtdna sequences  <cit> , and six different distances on  <dig> million base pairs of sampled ndna fragments from organisms of all major kingdoms of life  <cit> .
the performance of several distance functions has also been compared and benchmarked on their accuracy in constructing phylogenetic trees .
initially, cgr was used only for strings over a 4-letter alphabet , but generalizations have been proposed to peptide sequences , and almeida and vinga proposed a derivative of cgr called the universal sequence map , which is suitable for alphabets of any size  <cit> .
cgrs have also been subjected to multifractal analysis , see, e.g., .
lastly, cgr has been used to estimate sequence entropy , to speed up local-alignment algorithms  <cit> , and has been used together with neural networks to classify hpv genomes by genotype  <cit> .
several cgr studies  <cit>  observed that cgr patterns of nuclear and organellar dna sequences of the same organism can be completely different.
while the hypothesis that cgrs of mitochondrial dna sequences can play the role of genomic signatures was tested and validated on the set of all  <dig>  sequenced mitochondrial genomes  available in the ncbi genbank sequence database in july  <dig>  <cit> , to our knowledge no such extensive analysis of cgrs of nuclear/nucleoid genomic sequences exists to date.
the main contributions of this paper are:
we present an extensive analysis of the hypothesis that conventionally computed  ndna signatures can play the role of genomic signatures at multiple taxonomic levels, from kingdom to species.
our dataset totals  <dig>  gigabase pairs of ndna sequences from  <dig> different genomes, from all major kingdoms of life.
our analysis indicates that conventional ndna signatures of two different origins cannot always be differentiated, especially if they originate from closely related organisms.
to address this issue, we propose taking into account information obtained from organellar dna, in addition to ndna.
more generally, we propose the concept of an additive dna signature of a set  of dna sequences, and define two particular instances: composite dna signatures and assembled dna signatures.
we explore composite dna signatures, which combine conventional ndna signatures with organellar dna signatures  of the same organism.
we demonstrate that, in this dataset, the composite dna signatures originating from two different organisms can be differentiated in all cases, including those where the use of conventional ndna signatures failed.
in particular, composite dna signatures from genomes of species as closely related as h. sapiens and p. troglodytes, or e. coli and e. fergusonii, can be successfully separated.
we explore assembled dna signatures, which combine information from many short contigs  of a dna fragment to produce a recognizable signature.
this is in contrast to conventional dna signatures wherein one single long  dna sequence is needed to generate a recognizable signature.
the enhanced discriminating power of composite dna signatures, and the ability of assembled dna signatures to operate with scattered and reduced sequence data, open the possibility of practical applications including aiding species identification or classification, and comparisons of dna fragments of various origins such as genomes of extinct organisms, synthetic genomes, raw unassembled next-generation sequencing  read data, or even computer-generated dna sequences.
RESULTS
the first objective of this study was to test, on a comprehensive dataset, the hypothesis that conventional ndna signatures can be used to differentiate between nuclear dna sequences originating from different organisms, spanning all major kingdoms of life, at multiple taxonomic levels.
to this end, the following computational experiment was performed, for each of the major kingdoms of life, at various taxonomic levels.
we chose a pivot organism  and proceeded to use conventional ndna signatures to compare fragments of its nuclear/nucleoid genome with fragments of the nuclear/nucleoid genome of one other organism from the same kingdom.
the process was then repeated with the second organism being at increasing degrees of relatedness to the pivot organism.
more precisely, for each such pairwise comparison, the following three-step process was implemented.
randomly sample  <dig> kbp ndna fragments from every chromosome  of the two genomes involved in the comparison.
for each such ndna fragment, construct its corresponding conventional ndna signature using the process described in section “methods”.
compute pairwise distances for all pairs of conventional ndna signatures generated in step  <dig>  the distance used to start with was an approximated information distance , formally defined in section “methods” , since it is computationally simple and uses the least amount of sequence information.
if separation was not achieved using aid, five other distance measures were used: structural dissimilarity index   <cit> , euclidean distance, pearson correlation distance  <cit> , manhattan distance  <cit> , and descriptor distance  <cit> .
use the distance matrix obtained in step  <dig> as input to a multi-dimensional scaling  algorithm to produce a 3d molecular distance map  <cit> : each point in the map corresponds to  an ndna fragment from step  <dig>  and the geometric distance between every two points corresponds to the distance between the respective conventional ndna signatures in the distance matrix.
assess, for each molecular distance map, whether or not separation between conventional ndna signatures of dna fragments from the pivot organism and those from the other organism was achieved, by using either k-means clustering  <cit>  or by verifying the existence of a separating plane.
fig.
<dig> 3d molecular distance map illustrating interrelationships among conventional ndna signatures of  <dig> randomly sampled  <dig> kbp nuclear genomic fragments from h. sapiens  and  <dig> randomly sampled  <dig> kbp nuclear genomic fragments from d. melanogaster .
the accuracy of separation is  <dig>  %
the results for all kingdoms are presented in fig.
<dig>  and the corresponding 3d molecular distance maps can be found in  <cit> .
for kingdom animalia, the approximated information distance succeeded to separate h. sapiens  conventional ndna signatures from those of other organisms, down to and including from m. murinus  and t. syrichta .
in the cases marked y* in fig.
<dig>  while the accuracy was less than the threshold for separation , the existence of a separating plane was verified.
see discussion in section “methods” for details.
fig.
<dig> each subfigure summarizes, for a given kingdom, the results of pairwise comparisons between dna signatures of fragments from a pivot organism  and those from one other organism, at increasing levels of relatedness.
the first two result columns indicate the outcome of the comparisons of conventional ndna signatures, and the last two columns the comparisons of composite dna signatures.
green indicates that separation was achieved with aid, red indicates that separation was not achieved with any of the six distances listed in section “results”, and yellow  or y* indicate results discussed in the text.
the columns labelled acc % indicate the accuracy of the separations listed immediately at their left: a
c
c> <dig> % was considered separation.
a dash indicates that no sequenced data was available on ncbi/genbank at the time of this submission.
the corresponding 3d molecular distance maps for each of the comparisons can be found in  <cit>
the use of conventional ndna signatures failed to achieve separation for genomes of more closely related species.
in particular, it failed to separate conventional ndna signatures of h. sapiens from those of c. jacchus , p. anubis , n. leucogenys , p. abelii , g. gorilla .
for those organisms where separation was not achieved with approximated information distance, we performed the comparisons with the other five distances.
the results of these multiple computations were that, in all cases where approximated information distance failed to achieve separation, the other distances also failed.
fig.
<dig> 3d molecular distance map illustrating interrelationships among conventional ndna signatures of  <dig> randomly sampled nuclear genomic fragments from h. sapiens  and  <dig> randomly sampled nuclear genomic fragments from p. troglodytes .
all fragments are  <dig> kbp long, the accuracy of separation is  <dig>  %, and no separation plane could be found
for kingdom fungi, the pivot organism is the model organism saccharomyces cerevisiae , a species of yeast instrumental to winemaking, baking, and brewing.
separation of its conventional ndna signatures was achieved down to and including separation from c. dubliniensis .
in the case of the comparison with k. pastoris, marked with y* in fig.
<dig>  the accuracy score was lower than  <dig> %: this is an artifact of the shape of the 3d molecular distance map wherein one of the clusters has a trailing set of points that become erroneously separated by k-means from all the rest of the points.
because of this, and since the use of k-means on the 2d molecular distance map of the same dataset resulted in an accuracy score of  <dig> %, we interpreted this comparison as resulting in separation.
the results of the comparison between the conventional ndna signatures of the pivot organism and those of s. arboricola , were inconclusive: the use of euclidean and pearson distances resulted in separation , while the use of the other four distances  did not result in separation.
for kingdom plantae, the pivot organism is the model organism brassica napus , rapeseed, a flowering member of the family brassicaceae .
separation of its conventional ndna signatures was achieved down to and including separation from c. papaya .
for the comparisons with a. thaliana  and r. sativus , cluster separation was visually observed but not quantitatively confirmed by either k-means or plane separation.
the comparison with b. oleracea  did not result in separation, with any of the six distances.
for kingdom protista, the pivot organism is the model organism plasmodium falciparum, a protozoan parasite , one of the species of plasmodium that cause malaria in humans.
separation of its conventional ndna signatures from those of other organisms from the same kingdom was achieved at all taxonomic levels, down to and including separation from p. vivax .
for kingdom bacteria, the pivot organism is the model organism escherichia coli , a bacterium commonly found in the lower intestine of warm-blooded organisms.
separation of its conventional ndna signatures from those of other bacteria was successful down to and including separation from s. enterica , but failed with all six distances in the comparison with e. fergusonii .
for kingdom archaea, the pivot organism is the model organism pyrococcus furiosus , an extremophilic species of archaea.
separation of its conventional ndna signatures from those of other archaea was successful at all levels, down to and including separation from p. yayanosii .
the above results indicate that, especially in kingdom animalia, conventional ndna signatures cannot always be used to differentiate nuclear/nucleoid genomic sequences originating from two different genomes.
this suggests that conventional ndna signatures cannot always play the role of a “genomic signature”, particularly when the genomes being compared belong to closely related species.
composite dna signatures
to enhance the discriminating power of conventional ndna signatures, our second objective was to introduce and explore the concept of composite dna signatures, which combine conventional nuclear/nucleoid dna signatures with signatures of organellar genomes .
to test the discriminating power of composite dna signatures, we repeated all previous pairwise comparisons , using this time composite dna signatures.
the results are presented in the last two columns of fig.
<dig>
for kingdoms animalia, fungi and protista we used composite dna signatures combining the conventional ndna signature of each nuclear/nucleoid genomic fragment with that of the mtdna of the same organism .
using such composite dna signatures, differentiation of dna signatures by organism was successful in all cases, including all cases where the use of conventional ndna signature previously failed or was inconclusive.
see fig.
<dig>  versus fig.
<dig> .
fig.
<dig> 3d molecular distance map illustrating interrelationships among composite dna signatures using ndna and mtdna, of  <dig> dna fragments from h. sapiens  and  <dig> dna fragments from p. troglodytes .
the accuracy of separation is  <dig> %
to test the discriminating power of composite dna signatures using ndna, mtdna and cpdna, we employed them to perform comparisons for all genome pairs from kingdom plantae.
separation was achieved using all of: composite dna signatures using ndna and mtdna, composite dna signatures using ndna and cpdna, and composite dna signatures using ndna, mtdna, and cpdna.
see fig.
<dig> for the molecular distance maps illustrating the relationships between these signatures for b. napus and b. oleracea.
fig.
<dig> 3d molecular distance map illustrating interrelationships among signatures of  <dig> dna fragments from b. napus  and  <dig> dna fragments from b. oleracea  using a conventional ndna signatures, b composite dna signatures using ndna and mtdna, c composite dna signatures using ndna and cpdna, and d composite dna signatures using ndna, mtdna, and cpdna.
the accuracy of separation is  <dig>  % for , and  <dig> % for each of , , and
for kingdom bacteria, the use of composite dna signatures combining ndna and pdna  resulted in separation in all cases.
overall, the use of composite dna signatures resulted in separation in all pairwise comparisons in fig.
<dig> , including in those where the use of conventional ndna signature failed or resulted in inconclusive separations.
assembled dna signatures
as the third objective of this study, we explored a way to enhance the practical applicability of conventional dna signatures.
recall that, to produce a recognizable visual pattern that can be reliably used to represent a genome, a conventional dna signature needs as input a long contiguous  dna fragment.
this assumes a high quality and reliability of sequencing and assembly, which are not always available.
we propose instead to approximate a conventional signature by an assembled dna signature, which combines the conventional dna signatures of many short contigs  of the given fragment.
note that these contigs need not cover the entire dna fragment.
in what follows, we denote by |s| the length of the sequence s. given a dna fragment s, an assembled dna signature of s, using r equi-length contigs of length n , is defined as the sum of the conventional dna signatures of all of the r contigs.
a particular case of assembled dna signature is where the fragment s is partitioned into equi-length, consecutive, non-overlapping contigs, that is, s=s1s2…srsr+ <dig>  and |si|=n for 1≤i≤r, with |sr+1|<n.
in this case, we call the assembled signature a fully-assembled dna signature of the sequence s, using equi-length contigs of length n.
table  <dig>  through  – distances between the conventional ndna signature of a fragment and its assembled dna signatures, for various numbers r of contigs of the same length n:  distances to fully-assembled dna signatures;  theoretical upper bounds for ;  distances to assembled dna signatures;  same as , when tripling the number of contigs
n
r
r
r
r
through  – distances between the conventional ndna signature of a fragment and its assembled dna signatures, using variable-length contigs taken from a normal distribution n, with mean n and variance σ= <dig>  the ndna fragment used was from h. sapiens, chromosome  <dig>  fragment  <dig>
also as expected, for the same values of n and r, the distance between an assembled dna signature and the conventional ndna signature of the same fragment ) is higher than the one between a fully-assembled dna signature and the conventional ndna signature of the same fragment ).
this indicates that the assembled dna signature is less performant than the fully-assembled dna signature as an approximation of a conventional ndna signature.
the reason is that, given a fixed number r of contigs, in the case of an assembled dna signature the contigs are allowed to overlap and need not cover the entire fragment.
this can be compensated by increasing the coverage, that is, the number r of contigs.
table  <dig>   shows that tripling the number of contigs results in significantly smaller differences between assembled dna signatures and the conventional dna signature of the same fragment which they were meant to approximate.
the results in table  <dig> suggest that assembled dna signatures have the potential to play the role of “genomic signatures”, and be used directly on raw unassembled next-generation sequencing read data, or in cases where other methods are not directly applicable because high-quality sequencing data is not available.
to test this hypothesis, we considered the organism pairs in fig.
<dig> for which separation was obtained using conventional ndna signatures, and attempted to reproduce these successful separations using assembled dna signatures instead.
in addition, we empirically sought to find, in each case, the coverage  needed to achieve separation, as a percentage of total fragment length.
to determine the threshold interval where separation between assembled dna signatures of a given pair of organisms was achieved, when contigs of length n= <dig> were used, the following process was employed.
for various values of t, 0≤t≤ <dig> , we attempted to see if separation of assembled dna signatures from the two organisms was achieved, in the following way.
for each of the  <dig> kbp fragments s from the two genomes, q random positive integers were picked from the interval  <dig> to |s|−n+1=, where q=⌊t∗|s|/n⌋, that is, the integer part of t∗|s|/n.
these q numbers represent the start positions of the q chosen contigs.
for each contig start position, a contig of length n= <dig> was read and used for the assembled dna signature of the fragment s.
for each value of t, the corresponding 3d molecular distance map of the assembled dna signatures of the two organisms was then analyzed, by verifying the existence  of a separating plane.
the results are summarized in table  <dig> and can be interpreted as follows.
in the comparison between h. sapiens and d. melanogaster the threshold interval is  <dig> – <dig> %.
the lower limit of this interval is  <dig> %, and this means that in the computation using the coverage value t= <dig>  , separation was not achieved.
that is, for each of the  <dig> kbp ndna fragments available , when employing assembled ndna signatures using only  <dig> contigs per fragment , separation was not achieved.
the upper limit of the interval is  <dig> %, and this means that in the computation using the coverage value t= <dig>  , separation was achieved.
that is, when employing assembled ndna signatures using  <dig> contigs per fragment , separation was achieved.assembled ndna signatures: sequence coverage  needed for separation of the assembled ndna signatures of the pivot organism from assembled ndna signatures of the comparison organism, for all major kingdoms of life.
separations were confirmed by verifying the existence of separating planes
animalia
h.s
a
p
i
e
n
d.m
e
l
a
n
o
g
a
s
t
e
r
g.g
a
l
l
u
s
m.m
u
s
c
u
l
u
s
m.m
u
r
i
n
u
s
t.s
y
r
i
c
h
t
a
fungi
s.c
e
r
e
v
i
s
i
a
c.g
a
t
t
i
i
f.o
x
y
s
p
o
r
u
m
k.p
a
s
t
o
r
i
s
c.d
u
b
l
i
n
i
e
n
s
i
s
a
n
d
i
d
a
plantae
b.n
a
p
u
m.p
u
s
i
l
l
a
p.p
a
t
e
n
s
m.d
o
m
e
s
t
i
c
a
c.p
a
p
a
y
a
protista
p.f
a
l
c
i
p
a
r
u
o.t
r
i
f
a
l
l
a
x
t.g
o
n
d
i
i
t.o
r
i
e
n
t
a
l
i
s
p.v
i
v
a
x
i
v
a
x
bacteria
e.c
o
l
s.a
u
r
e
u
s
h.p
y
l
o
r
i
a.b
a
u
m
a
n
n
i
i
s.e
n
t
e
r
i
c
a
archaea
p.f
u
r
i
o
s
u
s.i
s
l
a
n
d
i
c
u
s
m.s
m
i
t
h
i
i
thermococcus
p.y
a
y
a
n
o
s
i
i
a
y
a
n
o
s
i
i
the actual threshold values lie in the intervals listed, and may be subject to the quality of the sequencing.
as expected, in general, the thresholds needed for separation increase with the increase in the degree of relatedness of the organisms being compared.
this suggests that ndna sequences from closely related organisms require a higher coverage  to be separated.
the only exception to this trend, in this dataset, were the pairs h. sapiens with m. murinus  requiring  <dig> – <dig> % sequence coverage, and h. sapiens and t. syrichta  requiring  <dig> – <dig> % sequence coverage.
thus, the  pair required higher sequence coverage to achieve separation than the  pair, even though the gray mouse lemur belongs to a different primate suborder  than the modern human, while the tarsier belongs to the same primate suborder as the modern human , and thus one would expect that more information would be needed to achieve the latter separation.
this apparent anomaly may be partly related to the fact that the phylogenetic placement of tarsiers within the order primates has been controversial for over a century  <cit> : in  <cit>  tarsiers are placed within haplorrhini, while according to  <cit> , mitochondrial dna evidence places tarsiiformes as a sister group to strepsirrhini.
composite-assembled dna signatures
we now briefly explore the potential of combining the approach of composite dna signatures with that of assembled dna signatures.
a composite-assembled dna signature is produced by combining information from the assembled dna signatures of two  different types of dna fragments.
for example, a composite-assembled signature using ndna and mtdna is obtained by combining the assembled ndna signature of one  <dig> kbp ndna fragment, with the assembled mtdna signature of the mtdna genome of the same organism.
fig.
<dig> 3d molecular distance map illustrating interrelationships among  <dig> composite  dna signatures, each using one ndna fragment and the mtdna genome from h. sapiens, blue ; and  <dig> composite  dna signatures, each using one ndna fragment and the mtdna genome from p. troglodytes, red ; for the composite-assembled dna signatures, the length of contigs was n= <dig>  while the number of contigs was  <dig>  for each  <dig> kbp ndna fragment, and  <dig>  for the human  mtdna genome.
the accuracy of separation between the h. sapiens and the p. troglodytes sequences was  <dig> %, but the existence of a separation plane was verified
CONCLUSIONS
the first objective of this paper was to conduct a comprehensive analysis, on a dataset totalling  <dig>  gb, of the hypothesis that chaos game representations of nuclear/nucleoid genomic sequences can play the role of “genomic signatures”, that is, that they are genome- and species-specific.
our results suggest that this hypothesis is not always valid, in that nuclear/nucleoid dna sequences belonging to closely related species such as h. sapiens and p. troglodytes or e. coli and e. fergusonii cannot always be separated using conventionally computed cgr signatures.
to address this issue, as a second objective, we propose the use of composite dna signatures, which combine information from the nuclear/nucleoid genome with that from one or more organellar genomes .
composite dna signatures were found, in this study, to result in successful separation of dna sequences by organism in all cases, including those where conventional ndna signatures failed.
as a third objective, we propose the use of assembled dna signatures, which combine information from short contigs  of a dna fragment, rather than using the entire contiguous fragment, to produce its signature.
we show that assembled dna signatures can be successful replacements of conventional dna signatures, and also that the composite and assembled dna signature approaches can be used simultaneously.
mathematically, composite and assembled dna signatures are both particular cases of a general concept, namely that of an additive dna signature of a set of dna sequences .
our results indicate that such additive dna signatures could be considered as potential candidates for the role of “genomic signatures” at various taxonomic levels, from distant to closely related species, and thus complement other methods for species identification and classification.
several directions of future research stem from the fact that existing literature indicates that the oligomer composition of nuclear/nucleoid dna sequences and mitochondrial dna sequences can be a source of taxonomic information.
such directions include testing the discriminating power of additive dna signatures in large-scale multi-genome comparisons, and exploring their utility in practical applications such as dna sequence identification and classification , metagenomics, and synthetic genomes.

 motivated by the general need to identify and classify species based on molecular evidence, alignment-free genome comparisons have been proposed, based on comparing chaos game representations of genomic dna sequences. the cgr of a dna sequence, proposed by jeffrey, is a graphical representation of a dna sequence, where the patterns in the image correspond to the frequencies of k-mers in the sequence. deschavanne et al. were the first to suggest that cgr is a good candidate for the role of “genomic signature” defined by karlin and burge as any specific quantitative characteristic of a sequence that is pervasive along the genome, while being dissimilar for sequences originating from organisms of different species. cgr is one of a variety of alignment-free methods that have been proposed for sequence and genome comparisons, as a computationally efficient approach that performs well even with dna sequences that have nothing or little in common., mtdna, cpdna, and pdna ). initially, cgr images were only qualitatively analyzed, and dutta et al. and goldman both advanced the suggestion that cgr images represent no more information than second-order markov chains, which was later disproven by almeida et al. and others. cgr has been applied extensively to phylogenetics together with the euclidean distance, for instance on ndna fragments from various domains, genomes from various genera, ndna fragments from several bird genomes, mtdna sequences, bacteria and about phages, hiv- genomes, mtdna sequences and ndna sequences from plants in the brassicales order. other distances have also been used, for instance the dssim image distance on a set of mtdna sequences, and six different distances on million base pairs of sampled ndna fragments from organisms of all major kingdoms of life. the performance of several distance functions has also been compared and benchmarked on their accuracy in constructing phylogenetic trees. initially, cgr was used only for strings over a 4-letter alphabet, but generalizations have been proposed to peptide sequences, and almeida and vinga proposed a derivative of cgr called the universal sequence map, which is suitable for alphabets of any size. cgrs have also been subjected to multifractal analysis, see, e.g.,. lastly, cgr has been used to estimate sequence entropy, to speed up local-alignment algorithms, and has been used together with neural networks to classify hpv genomes by genotype. several cgr studies observed that cgr patterns of nuclear and organellar dna sequences of the same organism can be completely different. while the hypothesis that cgrs of mitochondrial dna sequences can play the role of genomic signatures was tested and validated on the set of all sequenced mitochondrial genomes available in the ncbi genbank sequence database in july, to our knowledge no such extensive analysis of cgrs of nuclear/nucleoid genomic sequences exists to date. the main contributions of this paper are: we present an extensive analysis of the hypothesis that conventionally computed ndna signatures can play the role of genomic signatures at multiple taxonomic levels, from kingdom to species. our dataset totals gigabase pairs of ndna sequences from different genomes, from all major kingdoms of life. our analysis indicates that conventional ndna signatures of two different origins cannot always be differentiated, especially if they originate from closely related organisms. to address this issue, we propose taking into account information obtained from organellar dna, in addition to ndna. more generally, we propose the concept of an additive dna signature of a set of dna sequences, and define two particular instances: composite dna signatures and assembled dna signatures. we explore composite dna signatures, which combine conventional ndna signatures with organellar dna signatures of the same organism. we demonstrate that, in this dataset, the composite dna signatures originating from two different organisms can be differentiated in all cases, including those where the use of conventional ndna signatures failed. in particular, composite dna signatures from genomes of species as closely related as h. sapiens and p. troglodytes, or e. coli and e. fergusonii, can be successfully separated. we explore assembled dna signatures, which combine information from many short contigs of a dna fragment to produce a recognizable signature. this is in contrast to conventional dna signatures wherein one single long dna sequence is needed to generate a recognizable signature. the enhanced discriminating power of composite dna signatures, and the ability of assembled dna signatures to operate with scattered and reduced sequence data, open the possibility of practical applications including aiding species identification or classification, and comparisons of dna fragments of various origins such as genomes of extinct organisms, synthetic genomes, raw unassembled next-generation sequencing read data, or even computer-generated dna sequences.  the first objective of this study was to test, on a comprehensive dataset, the hypothesis that conventional ndna signatures can be used to differentiate between nuclear dna sequences originating from different organisms, spanning all major kingdoms of life, at multiple taxonomic levels. to this end, the following computational experiment was performed, for each of the major kingdoms of life, at various taxonomic levels. we chose a pivot organism and proceeded to use conventional ndna signatures to compare fragments of its nuclear/nucleoid genome with fragments of the nuclear/nucleoid genome of one other organism from the same kingdom. the process was then repeated with the second organism being at increasing degrees of relatedness to the pivot organism. more precisely, for each such pairwise comparison, the following three-step process was implemented. randomly sample kbp ndna fragments from every chromosome of the two genomes involved in the comparison. for each such ndna fragment, construct its corresponding conventional ndna signature using the process described in section “methods”. compute pairwise distances for all pairs of conventional ndna signatures generated in step the distance used to start with was an approximated information distance, formally defined in section “methods”, since it is computationally simple and uses the least amount of sequence information. if separation was not achieved using aid, five other distance measures were used: structural dissimilarity index, euclidean distance, pearson correlation distance, manhattan distance, and descriptor distance. use the distance matrix obtained in step as input to a multi-dimensional scaling algorithm to produce a 3d molecular distance map: each point in the map corresponds to an ndna fragment from step and the geometric distance between every two points corresponds to the distance between the respective conventional ndna signatures in the distance matrix. assess, for each molecular distance map, whether or not separation between conventional ndna signatures of dna fragments from the pivot organism and those from the other organism was achieved, by using either k-means clustering or by verifying the existence of a separating plane. fig. 3d molecular distance map illustrating interrelationships among conventional ndna signatures of randomly sampled kbp nuclear genomic fragments from h. sapiens and randomly sampled kbp nuclear genomic fragments from d. melanogaster. the accuracy of separation is % the results for all kingdoms are presented in fig. and the corresponding 3d molecular distance maps can be found in. for kingdom animalia, the approximated information distance succeeded to separate h. sapiens conventional ndna signatures from those of other organisms, down to and including from m. murinus and t. syrichta. in the cases marked y* in fig. while the accuracy was less than the threshold for separation, the existence of a separating plane was verified. see discussion in section “methods” for details. fig. each subfigure summarizes, for a given kingdom, the results of pairwise comparisons between dna signatures of fragments from a pivot organism and those from one other organism, at increasing levels of relatedness. the first two result columns indicate the outcome of the comparisons of conventional ndna signatures, and the last two columns the comparisons of composite dna signatures. green indicates that separation was achieved with aid, red indicates that separation was not achieved with any of the six distances listed in section “results”, and yellow or y* indicate results discussed in the text. the columns labelled acc % indicate the accuracy of the separations listed immediately at their left: a c c> % was considered separation. a dash indicates that no sequenced data was available on ncbi/genbank at the time of this submission. the corresponding 3d molecular distance maps for each of the comparisons can be found in the use of conventional ndna signatures failed to achieve separation for genomes of more closely related species. in particular, it failed to separate conventional ndna signatures of h. sapiens from those of c. jacchus, p. anubis, n. leucogenys, p. abelii, g. gorilla. for those organisms where separation was not achieved with approximated information distance, we performed the comparisons with the other five distances. the results of these multiple computations were that, in all cases where approximated information distance failed to achieve separation, the other distances also failed. fig. 3d molecular distance map illustrating interrelationships among conventional ndna signatures of randomly sampled nuclear genomic fragments from h. sapiens and randomly sampled nuclear genomic fragments from p. troglodytes. all fragments are kbp long, the accuracy of separation is %, and no separation plane could be found for kingdom fungi, the pivot organism is the model organism saccharomyces cerevisiae, a species of yeast instrumental to winemaking, baking, and brewing. separation of its conventional ndna signatures was achieved down to and including separation from c. dubliniensis. in the case of the comparison with k. pastoris, marked with y* in fig. the accuracy score was lower than %: this is an artifact of the shape of the 3d molecular distance map wherein one of the clusters has a trailing set of points that become erroneously separated by k-means from all the rest of the points. because of this, and since the use of k-means on the 2d molecular distance map of the same dataset resulted in an accuracy score of %, we interpreted this comparison as resulting in separation. the results of the comparison between the conventional ndna signatures of the pivot organism and those of s. arboricola, were inconclusive: the use of euclidean and pearson distances resulted in separation, while the use of the other four distances did not result in separation. for kingdom plantae, the pivot organism is the model organism brassica napus, rapeseed, a flowering member of the family brassicaceae. separation of its conventional ndna signatures was achieved down to and including separation from c. papaya. for the comparisons with a. thaliana and r. sativus, cluster separation was visually observed but not quantitatively confirmed by either k-means or plane separation. the comparison with b. oleracea did not result in separation, with any of the six distances. for kingdom protista, the pivot organism is the model organism plasmodium falciparum, a protozoan parasite, one of the species of plasmodium that cause malaria in humans. separation of its conventional ndna signatures from those of other organisms from the same kingdom was achieved at all taxonomic levels, down to and including separation from p. vivax. for kingdom bacteria, the pivot organism is the model organism escherichia coli, a bacterium commonly found in the lower intestine of warm-blooded organisms. separation of its conventional ndna signatures from those of other bacteria was successful down to and including separation from s. enterica, but failed with all six distances in the comparison with e. fergusonii. for kingdom archaea, the pivot organism is the model organism pyrococcus furiosus, an extremophilic species of archaea. separation of its conventional ndna signatures from those of other archaea was successful at all levels, down to and including separation from p. yayanosii. the above results indicate that, especially in kingdom animalia, conventional ndna signatures cannot always be used to differentiate nuclear/nucleoid genomic sequences originating from two different genomes. this suggests that conventional ndna signatures cannot always play the role of a “genomic signature”, particularly when the genomes being compared belong to closely related species. composite dna signatures to enhance the discriminating power of conventional ndna signatures, our second objective was to introduce and explore the concept of composite dna signatures, which combine conventional nuclear/nucleoid dna signatures with signatures of organellar genomes. to test the discriminating power of composite dna signatures, we repeated all previous pairwise comparisons, using this time composite dna signatures. the results are presented in the last two columns of fig. for kingdoms animalia, fungi and protista we used composite dna signatures combining the conventional ndna signature of each nuclear/nucleoid genomic fragment with that of the mtdna of the same organism. using such composite dna signatures, differentiation of dna signatures by organism was successful in all cases, including all cases where the use of conventional ndna signature previously failed or was inconclusive. see fig. versus fig.. fig. 3d molecular distance map illustrating interrelationships among composite dna signatures using ndna and mtdna, of dna fragments from h. sapiens and dna fragments from p. troglodytes. the accuracy of separation is % to test the discriminating power of composite dna signatures using ndna, mtdna and cpdna, we employed them to perform comparisons for all genome pairs from kingdom plantae. separation was achieved using all of: composite dna signatures using ndna and mtdna, composite dna signatures using ndna and cpdna, and composite dna signatures using ndna, mtdna, and cpdna. see fig. for the molecular distance maps illustrating the relationships between these signatures for b. napus and b. oleracea. fig. 3d molecular distance map illustrating interrelationships among signatures of dna fragments from b. napus and dna fragments from b. oleracea using a conventional ndna signatures, b composite dna signatures using ndna and mtdna, c composite dna signatures using ndna and cpdna, and d composite dna signatures using ndna, mtdna, and cpdna. the accuracy of separation is % for, and % for each of,, and for kingdom bacteria, the use of composite dna signatures combining ndna and pdna resulted in separation in all cases. overall, the use of composite dna signatures resulted in separation in all pairwise comparisons in fig., including in those where the use of conventional ndna signature failed or resulted in inconclusive separations. assembled dna signatures as the third objective of this study, we explored a way to enhance the practical applicability of conventional dna signatures. recall that, to produce a recognizable visual pattern that can be reliably used to represent a genome, a conventional dna signature needs as input a long contiguous dna fragment. this assumes a high quality and reliability of sequencing and assembly, which are not always available. we propose instead to approximate a conventional signature by an assembled dna signature, which combines the conventional dna signatures of many short contigs of the given fragment. note that these contigs need not cover the entire dna fragment. in what follows, we denote by |s| the length of the sequence s. given a dna fragment s, an assembled dna signature of s, using r equi-length contigs of length n, is defined as the sum of the conventional dna signatures of all of the r contigs. a particular case of assembled dna signature is where the fragment s is partitioned into equi-length, consecutive, non-overlapping contigs, that is, s=s1s2…srsr+ and |si|=n for 1≤i≤r, with |sr+1|<n. in this case, we call the assembled signature a fully-assembled dna signature of the sequence s, using equi-length contigs of length n. table through – distances between the conventional ndna signature of a fragment and its assembled dna signatures, for various numbers r of contigs of the same length n: distances to fully-assembled dna signatures; theoretical upper bounds for; distances to assembled dna signatures; same as, when tripling the number of contigs n r r r r through – distances between the conventional ndna signature of a fragment and its assembled dna signatures, using variable-length contigs taken from a normal distribution n, with mean n and variance σ= the ndna fragment used was from h. sapiens, chromosome fragment also as expected, for the same values of n and r, the distance between an assembled dna signature and the conventional ndna signature of the same fragment ) is higher than the one between a fully-assembled dna signature and the conventional ndna signature of the same fragment ). this indicates that the assembled dna signature is less performant than the fully-assembled dna signature as an approximation of a conventional ndna signature. the reason is that, given a fixed number r of contigs, in the case of an assembled dna signature the contigs are allowed to overlap and need not cover the entire fragment. this can be compensated by increasing the coverage, that is, the number r of contigs. table shows that tripling the number of contigs results in significantly smaller differences between assembled dna signatures and the conventional dna signature of the same fragment which they were meant to approximate. the results in table suggest that assembled dna signatures have the potential to play the role of “genomic signatures”, and be used directly on raw unassembled next-generation sequencing read data, or in cases where other methods are not directly applicable because high-quality sequencing data is not available. to test this hypothesis, we considered the organism pairs in fig. for which separation was obtained using conventional ndna signatures, and attempted to reproduce these successful separations using assembled dna signatures instead. in addition, we empirically sought to find, in each case, the coverage needed to achieve separation, as a percentage of total fragment length. to determine the threshold interval where separation between assembled dna signatures of a given pair of organisms was achieved, when contigs of length n= were used, the following process was employed. for various values of t, 0≤t≤, we attempted to see if separation of assembled dna signatures from the two organisms was achieved, in the following way. for each of the kbp fragments s from the two genomes, q random positive integers were picked from the interval to |s|−n+1=, where q=⌊t∗|s|/n⌋, that is, the integer part of t∗|s|/n. these q numbers represent the start positions of the q chosen contigs. for each contig start position, a contig of length n= was read and used for the assembled dna signature of the fragment s. for each value of t, the corresponding 3d molecular distance map of the assembled dna signatures of the two organisms was then analyzed, by verifying the existence of a separating plane. the results are summarized in table and can be interpreted as follows. in the comparison between h. sapiens and d. melanogaster the threshold interval is – %. the lower limit of this interval is %, and this means that in the computation using the coverage value t=, separation was not achieved. that is, for each of the kbp ndna fragments available, when employing assembled ndna signatures using only contigs per fragment, separation was not achieved. the upper limit of the interval is %, and this means that in the computation using the coverage value t=, separation was achieved. that is, when employing assembled ndna signatures using contigs per fragment, separation was achieved.assembled ndna signatures: sequence coverage needed for separation of the assembled ndna signatures of the pivot organism from assembled ndna signatures of the comparison organism, for all major kingdoms of life. separations were confirmed by verifying the existence of separating planes animalia h.s a p i e n d.m e l a n o g a s t e r g.g a l l u s m.m u s c u l u s m.m u r i n u s t.s y r i c h t a fungi s.c e r e v i s i a c.g a t t i i f.o x y s p o r u m k.p a s t o r i s c.d u b l i n i e n s i s a n d i d a plantae b.n a p u m.p u s i l l a p.p a t e n s m.d o m e s t i c a c.p a p a y a protista p.f a l c i p a r u o.t r i f a l l a x t.g o n d i i t.o r i e n t a l i s p.v i v a x i v a x bacteria e.c o l s.a u r e u s h.p y l o r i a.b a u m a n n i i s.e n t e r i c a archaea p.f u r i o s u s.i s l a n d i c u s m.s m i t h i i thermococcus p.y a y a n o s i i a y a n o s i i the actual threshold values lie in the intervals listed, and may be subject to the quality of the sequencing. as expected, in general, the thresholds needed for separation increase with the increase in the degree of relatedness of the organisms being compared. this suggests that ndna sequences from closely related organisms require a higher coverage to be separated. the only exception to this trend, in this dataset, were the pairs h. sapiens with m. murinus requiring – % sequence coverage, and h. sapiens and t. syrichta requiring – % sequence coverage. thus, the pair required higher sequence coverage to achieve separation than the pair, even though the gray mouse lemur belongs to a different primate suborder than the modern human, while the tarsier belongs to the same primate suborder as the modern human, and thus one would expect that more information would be needed to achieve the latter separation. this apparent anomaly may be partly related to the fact that the phylogenetic placement of tarsiers within the order primates has been controversial for over a century: in tarsiers are placed within haplorrhini, while according to, mitochondrial dna evidence places tarsiiformes as a sister group to strepsirrhini. composite-assembled dna signatures we now briefly explore the potential of combining the approach of composite dna signatures with that of assembled dna signatures. a composite-assembled dna signature is produced by combining information from the assembled dna signatures of two different types of dna fragments. for example, a composite-assembled signature using ndna and mtdna is obtained by combining the assembled ndna signature of one kbp ndna fragment, with the assembled mtdna signature of the mtdna genome of the same organism. fig. 3d molecular distance map illustrating interrelationships among composite dna signatures, each using one ndna fragment and the mtdna genome from h. sapiens, blue; and composite dna signatures, each using one ndna fragment and the mtdna genome from p. troglodytes, red; for the composite-assembled dna signatures, the length of contigs was n= while the number of contigs was for each kbp ndna fragment, and for the human mtdna genome. the accuracy of separation between the h. sapiens and the p. troglodytes sequences was %, but the existence of a separation plane was verified  the first objective of this paper was to conduct a comprehensive analysis, on a dataset totalling gb, of the hypothesis that chaos game representations of nuclear/nucleoid genomic sequences can play the role of “genomic signatures”, that is, that they are genome- and species-specific. our results suggest that this hypothesis is not always valid, in that nuclear/nucleoid dna sequences belonging to closely related species such as h. sapiens and p. troglodytes or e. coli and e. fergusonii cannot always be separated using conventionally computed cgr signatures. to address this issue, as a second objective, we propose the use of composite dna signatures, which combine information from the nuclear/nucleoid genome with that from one or more organellar genomes. composite dna signatures were found, in this study, to result in successful separation of dna sequences by organism in all cases, including those where conventional ndna signatures failed. as a third objective, we propose the use of assembled dna signatures, which combine information from short contigs of a dna fragment, rather than using the entire contiguous fragment, to produce its signature. we show that assembled dna signatures can be successful replacements of conventional dna signatures, and also that the composite and assembled dna signature approaches can be used simultaneously. mathematically, composite and assembled dna signatures are both particular cases of a general concept, namely that of an additive dna signature of a set of dna sequences. our results indicate that such additive dna signatures could be considered as potential candidates for the role of “genomic signatures” at various taxonomic levels, from distant to closely related species, and thus complement other methods for species identification and classification. several directions of future research stem from the fact that existing literature indicates that the oligomer composition of nuclear/nucleoid dna sequences and mitochondrial dna sequences can be a source of taxonomic information. such directions include testing the discriminating power of additive dna signatures in large-scale multi-genome comparisons, and exploring their utility in practical applications such as dna sequence identification and classification, metagenomics, and synthetic genomes. 
studies exploring the potential of chaos game representations of genomic sequences to act as “genomic signatures” showed that cgr patterns of nuclear and organellar dna sequences of the same organism can be very different. while the hypothesis that cgrs of mitochondrial dna sequences can act as genomic signatures was validated for a snapshot of all sequenced mitochondrial genomes available in the ncbi genbank sequence database, to our knowledge no such extensive analysis of cgrs of nuclear dna sequences exists to date. to address this issue, we propose the general concept of additive dna signature of a set of dna sequences. one particular instance, the composite dna signature, combines information from ndna fragments and organellar genomes. we demonstrate that, in this dataset, composite dna signatures originating from two different organisms can be differentiated in all cases, including those where the use of cgr signatures of ndna failed or was inconclusive. another instance, the assembled dna signature, combines information from many short dna subfragments of a given dna fragment, to produce its signature. we show that an assembled dna signature has the same distinguishing power as a conventionally computed cgr signature, while using shorter contiguous sequences and potentially less sequence information. our results suggest that, while cgr signatures of ndna cannot always play the role of genomic signatures, composite and assembled dna signatures could potentially be used instead. comparative genomicsalignment-freegenomic signaturechaos game representationinformation distanceadditive dna signaturecomposite dna signatureassembled dna signaturenatural sciences and engineering research council of canada r2824a01kari lila http://dx.doi.org/ /501100000038natural sciences and engineering research council of canada220259konstantinidis stavros http://dx.doi.org/ /501100000038natural sciences and engineering research council of canada480936kopecki steffen issue-copyright-statement© the author 2016 our computational experiments indicate that cgr signatures of ndna of two different origins cannot always be differentiated, especially if they originate from closely-related species such as h. sapiens and p. troglodytes or e. coli and e. fergusonii. we analyzed an extensive dataset, totalling gigabase pairs, of nuclear/nucleoid genomic sequences from different organisms, spanning all major kingdoms of life. such additive signatures could be used, e.g., with raw unassembled next-generation sequencing read data, when high-quality sequencing data is not available, or to complement information obtained by other methods of species identification or classification.
 studies exploring the potential of chaos game representations of genomic sequences to act as “genomic signatures” showed that cgr patterns of nuclear and organellar dna sequences of the same organism can be very different. while the hypothesis that cgrs of mitochondrial dna sequences can act as genomic signatures was validated for a snapshot of all sequenced mitochondrial genomes available in the ncbi genbank sequence database, to our knowledge no such extensive analysis of cgrs of nuclear dna sequences exists to date.  we analyzed an extensive dataset, totalling gigabase pairs, of nuclear/nucleoid genomic sequences from different organisms, spanning all major kingdoms of life. our computational experiments indicate that cgr signatures of ndna of two different origins cannot always be differentiated, especially if they originate from closely-related species such as h. sapiens and p. troglodytes or e. coli and e. fergusonii. to address this issue, we propose the general concept of additive dna signature of a set of dna sequences. one particular instance, the composite dna signature, combines information from ndna fragments and organellar genomes. we demonstrate that, in this dataset, composite dna signatures originating from two different organisms can be differentiated in all cases, including those where the use of cgr signatures of ndna failed or was inconclusive. another instance, the assembled dna signature, combines information from many short dna subfragments of a given dna fragment, to produce its signature. we show that an assembled dna signature has the same distinguishing power as a conventionally computed cgr signature, while using shorter contiguous sequences and potentially less sequence information.  our results suggest that, while cgr signatures of ndna cannot always play the role of genomic signatures, composite and assembled dna signatures could potentially be used instead. such additive signatures could be used, e.g., with raw unassembled next-generation sequencing read data, when high-quality sequencing data is not available, or to complement information obtained by other methods of species identification or classification. electronic supplementary material the online version of this article contains supplementary material, which is available to authorized users. keywords comparative genomicsalignment-freegenomic signaturechaos game representationinformation distanceadditive dna signaturecomposite dna signatureassembled dna signaturenatural sciences and engineering research council of canada r2824a01kari lila http://dx.doi.org/ /501100000038natural sciences and engineering research council of canada220259konstantinidis stavros http://dx.doi.org/ /501100000038natural sciences and engineering research council of canada480936kopecki steffen issue-copyright-statement© the author 2016 