BACKGROUND
the package gennon-h presented here simulates dna sequences evolving on a given phylogenetic tree directly from the transition matrices.
in other words, the goal of developing gennon-h was to generate dna sequences following discrete-time markov models on a given phylogenetic tree .
given a phylogenetic tree t, the parameters of these models are the root distribution and the substitution matrices pe assigned to each edge e of t. the entries of pe correspond to the conditional probabilities p that a nucleotide y at the parent node of e is substituted by nucleotide x at the child node .
there is no extra restriction on these matrices, in contrast to continuous-time processes, where the substitution matrices are the exponential of a rate matrix q multiplied by the number of events.
whereas generating matrices of type exp with a preassigned number of substitutions  is relatively easy, the task of generating  markov matrices with a preassigned expected number of substitutions per site has been recently solved in
<cit> .
the software gennon-h is implemented for the  jukes-cantor jc <dig>  kimura two k <dig> and three k <dig> parameters, strand symmetric ssm, and general markov models gmm.
the shape of the substitution matrices  for jc <dig>  k <dig>  k <dig>  ssm and gmm models is given by:
abbbbabbbbabbbbaabcbbabccbabbcbaabcdbadccdabdcba
abcdefghhgfedcbaabcdefghijklmnop.
for these models, the algorithms given in
<cit>  can generate any stochastic matrix corresponding to a given branch length .
we refer the reader to
<cit>  for more details and references of these models.
in the continuous-time models, the process is often assumed to be homogeneous  and the rate matrix q is common throughout the entire tree.
this is not an implicit hypothesis for the discrete-time markov processes, thus the evolutionary processes simulated using gennon-h are nonhomogeneous.
although a variety of methods exist for simulating alignments under the continuous-time models , we provide the first software for generating multiple sequence alignments evolving under the discrete-time markov processes on trees.
other powerful software include the bayesian phylogenetic methods of
<cit>  and
<cit> .
mrbayes <cit>  is a robust inference and model selection method, which provides a variety of tools for nucleotide and amino-acid data analysis.
beast <cit>  enables to generate msa with rate matrices differing at distinct edges.
however, both packages are based on the rate-based continuous-time models for nucleotide data and as such, assume the exponential form of the substitution matrices.
this in turn restricts the space of possible matrices assigned to a given edge length.
gennon-h, which aims to explore the space of all matrices, mimics the stochastic character of evolution as attempted to be captured by mathematical models.
gennon-h is the first software tailored specifically for the purpose of generating the dna sequence alignments evolving on phylogenetic trees under the nonhomogeneous models.
gennon-h does not aim to replace the existing methods, but to serve as an option for researchers, whose interest lies in testing the performance of the algorithms on data generated under the assumption of more general models.
a newly created software empar , enables to infer the parameters of the model considered in this work.
it is worth pointing out that the strand symmetric model and the general markov model considered in gennon-h do not lie in the class of stationary models, which adds to the flexibility of the framework presented here.
as a comparison, we note that the software packages that are prevalently in use consider only stationary and time-reversible models.
this is due to the fact that the continuous-time models require computing exponentials of rate matrices, which is a nontrivial task for a general matrix.
this contributes to the practice of using the time-reversible rate-based models irrespective of the setting under consideration.
as shown in
<cit> , the substitution parameters for the gmm model , are identifiable up to permutation.
in gennon-h we fabricate matrices of the diagonal largest in column  type
<cit> , whenever possible, i.e.
matrices whose largest entry in every column is placed on the diagonal.
dlc matrices share an important feature of being identifiable– there exists a unique set of substitution matrices satisfying the dlc condition and a unique root distribution that leads to the given joint distribution at the leaves.
in other words, the data generated from the dlc matrices and sufficient alignment lengths have high likelihood of being identifiable and therefore can be safely used to test hypotheses about the tree or the data.
implementation
gennon-h has been implemented in c++.
its input is a tree in the newick format  with annotated branch lengths.
other arguments include the base name of the output files, length of the alignment and a model.
an exemplary command-line input is:
./gennon-h treefilename outputfilename length modelname
for instance, if ‘tree.txt’ is a text file consisting a newick 5-taxon phylogenetic tree:
: <dig> ,species4: <dig> ,species5: <dig> ),
then the following command line input
./gennon-h tree.txt data.fa  <dig> k81
generates a msa of length  <dig> nt evolving on the tree given in ‘ tree.txt’ under the k <dig> model.
the result is recorded it in the file ‘data.fa’.
the algorithm proceeds as follows:
input: a discrete-time markov model
m, a phylogenetic tree
t with assigned branch lengths in the newick format, and an alignment length l;
step 1: generate a dna sequence s0of length l at the root of
t according to distribution of the model
m;
step 2: for each edge e in
t, using
<cit> , we generate a matrix pe of the type
m corresponding to the length le of edge e ).
if the resulting matrix is not dlc, we apply a permutation of rows to convert it to a dlc matrix.
every model has a set of permutations allowable, such that the form of the matrix dictated by the model is maintained.
if neither of the permutations creates a dlc matrix, we generate a new matrix pe and repeat the procedure.
we limited the number of trials to  <dig> before the simulations require a re-start, however, in practice a dlc matrix is expected to be found in much fewer iterations;
step 3: we let s <dig> evolve according to the corresponding markov process on
t;
output: a multiple sequence alignment and the substitution matrices used for its simulation.
the output files constitute both a fasta file with a multiple sequence alignment simulated on
t, and a file listing the parameters used for the simulations of the data.
the order of the output matrices corresponds to the order in which the branches of the newick tree are read: terminal edges are put first, followed by the top-down listing of the edges starting at the root .
RESULTS
the c++ implementation of gennon-h can be accessed at the project home page
http://genome.crg.es/cgi-bin/phylo_mod_sel/alggennonh.pl, at sourceforge, or in the additional file
<dig> accompanying this paper.
the algorithm has been successfully used in
<cit>  to test a new model selection method based on  <dig> and 6-taxon dna multiple sequence alignments.
the size of the tree is not a limiting factor to the use of the code as the execution time grows linearly in the number of taxa, thus the method can be used to generate data of any size.
in order to test the speed of gennon-h, we investigated the times it took to generate  <dig> alignments of  <dig> nt on the following 5-taxa tree : <dig> ,seq4: <dig> ,seq5: <dig> ).
the results are given in table
<dig>
the simulated data saved in the output files together with the parameters used for its simulation are suited for hypothesis testing in a variety of biological applications.
CONCLUSIONS
gennon-h is the first software simulating dna sequences directly from the transition matrices computed from the branch lengths of a given phylogenetic tree.
it implements discrete-time markov processes on phylogenetic trees on any number of taxa.
in the current release the support was given to the most well-known discrete-time markov models: the jukes-cantor, kimura  <dig> and  <dig> parameters, strand symmetric and general markov models.
the possibility of generating nonhomogeneous  or nonstationary  processes makes the method particularly appealing when handling complex biological questions.
availability and requirements
project name: gennon-h
project home page:
http://genome.crg.es/cgi-bin/phylo_mod_sel/alggennonh.pl; also available from sourceforge
https://sourceforge.net/projects/gennonh/, and as additional file
1
operating systems: platform independent
programming language: c++
other requirements: gnu gcc compiler, version  <dig> .
<dig> of the boost library
distributed under the gnu general public license
abbreviations
jc69: discrete-time jukes-cantor model; k80: discrete-time kimura 2-parameter model; k81: discrete-time kimura 3-parameter model; ssm: strand symmetric model; gmm: general markov model.
competing interest
both authors declare that they have no competing interests.
author’s contributions
ak created and tested the software, established a platform for its usage and drafted part of the manuscript.
mc conceived of the project and drafted part of the manuscript.
both authors read and approved the final manuscript and declare no conflicts of interests.
supplementary material
additional file 1
is a zipped  file containing the c++ implementation of gennon-h.
click here for file
acknowledgements
both authors were partially supported by generalitat de catalunya,  <dig> sgr  <dig>  mc is partially supported by ministerio de educación y ciencia mtm2009-14163-c02- <dig>

 the package gennon-h presented here simulates dna sequences evolving on a given phylogenetic tree directly from the transition matrices. in other words, the goal of developing gennon-h was to generate dna sequences following discrete-time markov models on a given phylogenetic tree. given a phylogenetic tree t, the parameters of these models are the root distribution and the substitution matrices pe assigned to each edge e of t. the entries of pe correspond to the conditional probabilities p that a nucleotide y at the parent node of e is substituted by nucleotide x at the child node. there is no extra restriction on these matrices, in contrast to continuous-time processes, where the substitution matrices are the exponential of a rate matrix q multiplied by the number of events. whereas generating matrices of type exp with a preassigned number of substitutions is relatively easy, the task of generating markov matrices with a preassigned expected number of substitutions per site has been recently solved in. the software gennon-h is implemented for the jukes-cantor jc kimura two k and three k parameters, strand symmetric ssm, and general markov models gmm. the shape of the substitution matrices for jc k k ssm and gmm models is given by: abbbbabbbbabbbbaabcbbabccbabbcbaabcdbadccdabdcba abcdefghhgfedcbaabcdefghijklmnop. for these models, the algorithms given in can generate any stochastic matrix corresponding to a given branch length. we refer the reader to for more details and references of these models. in the continuous-time models, the process is often assumed to be homogeneous and the rate matrix q is common throughout the entire tree. this is not an implicit hypothesis for the discrete-time markov processes, thus the evolutionary processes simulated using gennon-h are nonhomogeneous. although a variety of methods exist for simulating alignments under the continuous-time models, we provide the first software for generating multiple sequence alignments evolving under the discrete-time markov processes on trees. other powerful software include the bayesian phylogenetic methods of and. mrbayes is a robust inference and model selection method, which provides a variety of tools for nucleotide and amino-acid data analysis. beast enables to generate msa with rate matrices differing at distinct edges. however, both packages are based on the rate-based continuous-time models for nucleotide data and as such, assume the exponential form of the substitution matrices. this in turn restricts the space of possible matrices assigned to a given edge length. gennon-h, which aims to explore the space of all matrices, mimics the stochastic character of evolution as attempted to be captured by mathematical models. gennon-h is the first software tailored specifically for the purpose of generating the dna sequence alignments evolving on phylogenetic trees under the nonhomogeneous models. gennon-h does not aim to replace the existing methods, but to serve as an option for researchers, whose interest lies in testing the performance of the algorithms on data generated under the assumption of more general models. a newly created software empar, enables to infer the parameters of the model considered in this work. it is worth pointing out that the strand symmetric model and the general markov model considered in gennon-h do not lie in the class of stationary models, which adds to the flexibility of the framework presented here. as a comparison, we note that the software packages that are prevalently in use consider only stationary and time-reversible models. this is due to the fact that the continuous-time models require computing exponentials of rate matrices, which is a nontrivial task for a general matrix. this contributes to the practice of using the time-reversible rate-based models irrespective of the setting under consideration. as shown in, the substitution parameters for the gmm model, are identifiable up to permutation. in gennon-h we fabricate matrices of the diagonal largest in column type, whenever possible, i.e. matrices whose largest entry in every column is placed on the diagonal. dlc matrices share an important feature of being identifiable– there exists a unique set of substitution matrices satisfying the dlc condition and a unique root distribution that leads to the given joint distribution at the leaves. in other words, the data generated from the dlc matrices and sufficient alignment lengths have high likelihood of being identifiable and therefore can be safely used to test hypotheses about the tree or the data. implementation gennon-h has been implemented in c++. its input is a tree in the newick format with annotated branch lengths. other arguments include the base name of the output files, length of the alignment and a model. an exemplary command-line input is:./gennon-h treefilename outputfilename length modelname for instance, if ‘tree.txt’ is a text file consisting a newick 5-taxon phylogenetic tree::,species4:,species5: ), then the following command line input./gennon-h tree.txt data.fa k81 generates a msa of length nt evolving on the tree given in ‘ tree.txt’ under the k model. the result is recorded it in the file ‘data.fa’. the algorithm proceeds as follows: input: a discrete-time markov model m, a phylogenetic tree t with assigned branch lengths in the newick format, and an alignment length l; step 1: generate a dna sequence s0of length l at the root of t according to distribution of the model m; step 2: for each edge e in t, using, we generate a matrix pe of the type m corresponding to the length le of edge e ). if the resulting matrix is not dlc, we apply a permutation of rows to convert it to a dlc matrix. every model has a set of permutations allowable, such that the form of the matrix dictated by the model is maintained. if neither of the permutations creates a dlc matrix, we generate a new matrix pe and repeat the procedure. we limited the number of trials to before the simulations require a re-start, however, in practice a dlc matrix is expected to be found in much fewer iterations; step 3: we let s evolve according to the corresponding markov process on t; output: a multiple sequence alignment and the substitution matrices used for its simulation. the output files constitute both a fasta file with a multiple sequence alignment simulated on t, and a file listing the parameters used for the simulations of the data. the order of the output matrices corresponds to the order in which the branches of the newick tree are read: terminal edges are put first, followed by the top-down listing of the edges starting at the root.  the c++ implementation of gennon-h can be accessed at the project home page http://genome.crg.es/cgi-bin/phylo_mod_sel/alggennonh.pl, at sourceforge, or in the additional file accompanying this paper. the algorithm has been successfully used in to test a new model selection method based on and 6-taxon dna multiple sequence alignments. the size of the tree is not a limiting factor to the use of the code as the execution time grows linearly in the number of taxa, thus the method can be used to generate data of any size. in order to test the speed of gennon-h, we investigated the times it took to generate alignments of nt on the following 5-taxa tree:,seq4:,seq5: ). the results are given in table the simulated data saved in the output files together with the parameters used for its simulation are suited for hypothesis testing in a variety of biological applications.  gennon-h is the first software simulating dna sequences directly from the transition matrices computed from the branch lengths of a given phylogenetic tree. it implements discrete-time markov processes on phylogenetic trees on any number of taxa. in the current release the support was given to the most well-known discrete-time markov models: the jukes-cantor, kimura and parameters, strand symmetric and general markov models. the possibility of generating nonhomogeneous or nonstationary processes makes the method particularly appealing when handling complex biological questions. availability and requirements project name: gennon-h project home page: http://genome.crg.es/cgi-bin/phylo_mod_sel/alggennonh.pl; also available from sourceforge https://sourceforge.net/projects/gennonh/, and as additional file 1 operating systems: platform independent programming language: c++ other requirements: gnu gcc compiler, version. of the boost library distributed under the gnu general public license abbreviations jc69: discrete-time jukes-cantor model; k80: discrete-time kimura 2-parameter model; k81: discrete-time kimura 3-parameter model; ssm: strand symmetric model; gmm: general markov model. competing interest both authors declare that they have no competing interests. author’s contributions ak created and tested the software, established a platform for its usage and drafted part of the manuscript. mc conceived of the project and drafted part of the manuscript. both authors read and approved the final manuscript and declare no conflicts of interests. supplementary material additional file 1 is a zipped file containing the c++ implementation of gennon-h. click here for file acknowledgements both authors were partially supported by generalitat de catalunya, sgr mc is partially supported by ministerio de educación y ciencia mtm2009-14163-c02- 
a number of software packages are available to generate dna multiple sequence alignments evolved under continuous-time markov processes on phylogenetic trees. we present the first package designed to generate msas evolving under discrete-time markov processes on phylogenetic trees, directly from probability substitution matrices. based on the input model and a phylogenetic tree in the newick format, the algorithm produces dna alignments of desired length. the software presented here is an efficient tool to generate dna msas on a given phylogenetic tree. moreover, existing software restricts to the time-reversible models and it is not optimized to generate nonhomogeneous data. on the other hand, methods of simulating the dna msa directly from the transition matrices do not exist.
 a number of software packages are available to generate dna multiple sequence alignments evolved under continuous-time markov processes on phylogenetic trees. on the other hand, methods of simulating the dna msa directly from the transition matrices do not exist. moreover, existing software restricts to the time-reversible models and it is not optimized to generate nonhomogeneous data.  we present the first package designed to generate msas evolving under discrete-time markov processes on phylogenetic trees, directly from probability substitution matrices. based on the input model and a phylogenetic tree in the newick format, the algorithm produces dna alignments of desired length. gennon-h is publicly available for download.  the software presented here is an efficient tool to generate dna msas on a given phylogenetic tree. gennon-h provides the user with the nonstationary or nonhomogeneous phylogenetic data that is well suited for testing complex biological hypotheses, exploring the limits of the reconstruction algorithms and their robustness to such models. 