the study of k - string composition of long dna sequences including complete genomes is a natural extension of g + c content , i.e. , k = 1 , analysis .
using k values greater than 1 takes into account short - range ( up to k  1 ) correlations of nucleotides and enhances species - specific features in the sequence .
visualization of the k - string distribution on a computer screen using a crude color code is essentially a kind of coarse - graining that helps to highlight some prominent feature of the dna sequence .
for example , short palindromic strings of a certain type are avoided or under - represented in some bacterial genomes , leading to quite specific 2d histograms , while in mammalian genomic sequences the lower content of the dinucleotide cg as compared to gc dominates the picture 1 . , 2 .. two - dimensional portraits of the human chromosome 22 and the genomes of three bacteria are given in figure 1 .
the similar patterns in the portraits of escherichia coli and shigella flexneri are caused by the under - representation of strings that contain ctag as substrings .
the species - specific  avoidance signature  of complete bacterial genomes has eventually led to a new way of inferring phylogenetic relationship of prokaryotes without sequence alignment 3 . , 4 .. studies of the 1d histograms of extant complete genomes in contrast to their random counterparts have revealed the existence of universal length in complete genomes that can be explained by a simple universal model for genome growth and evolution 5 . , 6 .. in order to see that an observed feature does not occur in a random sequence , it is desirable to have randomization function built - in .
a seemingly surprising effect is the appearance of fine structures in some randomized prokaryotic genomes with significant g + c bias . in figure 2 , the 1d histograms for k = 4 to 9 are shown for mycobacterium tuberculosis whose g and c make 65.6% of the genome . at fixed k , a total of k
+ 1 peaks can be seen in the histogram . this phenomenon has been fully understood .
in particular , each peak may be well approximated by a poisson distribution ( 7 ) .
the visualization tool used by us to obtain the aforementioned results in the cited papers has been improved over the years . from a unix command line tool for 2d histograms based on xlib and xtoolkit ( the old code is available at request to the corresponding author ) , it has evolved into a linux software using the gtk+ package with a user - friendly graphic interface .
in order to count the frequency of occurrence of k - strings , a total of 4 counters are needed . to visualize the frequency distribution ,
these counters are allocated in a 2  2 square matrix and a color code is used to show the range of counting .
the allocation of counters is realized by taking the direct product of k copies of the 2  2 matrix ( 1)(gcat).we put g and c in the first row to make the effect of g+c content readily visible .
what we obtain is a 2d histogram or a  portrait  of the dna sequence .
a 1d histogram is constructed by putting the counts along the abscissa from a minimal ( may be zero ) to a maximal count and the number of string types within a narrow range ( a bin ) of counts along the ordinate . to provide a reference for comparison , the program can randomize the input sequence , keeping the number of each type of nucleotides unchanged .
the program takes one or more dna sequences in either genbank or fasta format as input .
the user may form a list of sequences and then work with them to conduct comparative studies .
seedna displays 2d as well as 1d histograms of the designated sequence or its reverse - conjugate or both ( by concatenating them ) using the original input or its randomized counterpart .
using k greater than 9 would extend the picture beyond the screen of most present - day computers .
the cursor will cause the designated string and its count ( 2d ) or the count range and the number of string types whose counts fall in that range ( 1d ) to be displayed .
the 2d histograms of closely related species show strong similarities in k - string composition .
this is clearly seen in the two lower portraits of figure 1 and the portrait of figure 3c , as e. coli , s. flexneri and s. typhi all belong to the same family enterobacteriaceae .
therefore , it makes sense to display the difference of counts for each string type . to put the comparison on equal footing ,
then the two counts c1 and c2 for the same string type are used to calculate ( c1  c2)/(c1 + c2 ) .
the last ratio is displayed using seven colors for the ranges ( 0.01 , 0.01 ) , (0.01 , 0.1 ) , (0.1 , 0.5 ) , and (0.5 , 1 ) . the string and its counts c1 and c2 are shown interactively at the bottom of the graph .
this comparison feature is experimental for the time being and the way of showing the difference of  portraits  will be improved as more applications are implemented .
for example , the user may change the color code or determine how many times the randomization procedure would be applied to the sequence before it is treated . at the users choice
a screen figure may be exported to a gif file under a separate name for later manipulation .
besides our old unix code , a very limited version of the 2d histogram was implemented at the european bioinformatics institute ( ebi ; http://industry.ebi.ac.uk/openbsa/bsa_viewers/ ) and the national institute for standard and technology ( nist ; http://math.nist.gov/~fhunt/genpatterns/ ) .
these implementations did not provide built - in randomization , 1d histogram and comparison of 2d histograms .
our full - fledged seedna program is written in c language using the gtk+ graphic package .
a user - friendly interface makes the choice or combination of features a matter of clicking on buttons .
the 2d histograms , if shown only in black / white , look similar to the chaos game representation ( cgr ) of dna sequence 8 .
, 9 .. the chaos program in the free emboss package ( 10 ) implements the cgr algorithm .
the consistency of the  limiting measure  of cgr and seedna algorithms has been analyzed by tin ( 11 ) .
however , the seedna realizes the visualization of  density  in one pass , keeping the resolution k fixed .
this can not be done in cgr without changing the algorithm and program . moreover , due to finite resolution of the computer screen the actual k is out of control and it varies along different directions in the cgr .
therefore , seedna may replace chaos entirely with many new features added ( 1d histogram , randomization , comparison of 2d histograms , etc . ) .
the source code of seedna is freely available under the gnu general public license at the authors website ( www.itp.ac.cn/~hao/seedna.tar.gz ; http://tlife.fudan.edu.cn/seedna.tar.gz ) .
installation and running information as well as references are included as separate files in the above release package .
since the definition of direct product of matrices applies to rectangular matrices as well , the idea of using direct product of matrices to represent k - strings may also be extended to protein sequences .
we may define a 4  5 matrix ( 12)x=(acdefghiklmnpqrstvwy),where the matrix elements are the one - letter abbreviation of the amino acids .
however , a similar visualization scheme would only work for k  4 if one does not scroll the picture behind the screen . furthermore , as protein sequences are much shorter than nucleic acids , the highlight of visualization must come from those strings that are present instead of those missing .
 an interactive tool to visualize the k - string composition of long dna sequences including bacterial complete genomes is described . 
 it is especially useful for exploring short palindromic structures in the sequences . 
 the seedna program runs on red hat linux with gtk+ support . 
 it displays two - dimensional ( 2d ) or one - dimensional ( 1d ) histograms of the k - string distribution of a given sequence and/or its randomized counterpart . 
 it is also capable of showing the difference of k - string distributions between two sequences . 
 the c source code using the gtk+ package is freely available . 
Introduction
Algorithm and Features
Implementation and Availability