Evolution and Phylogenetics
Using median sets for inferring phylogenetic trees
Parallel Computing and Complex Systems Group, Department of Computer Science, University of Leipzig Augustusplatz 10/11, 04109 Leipzig, Germany
*To whom correspondence should be addressed.
 |
ABSTRACT |
|---|
 TOP ABSTRACT 1 INTRODUCTION2 BASIC DEFINITIONS3 INFERRING PHYLOGENETIC TREES4 GRAPPA AND MGR5 ALGORITHM amGRP6 EXPERIMENTS7 CONCLUSIONREFERENCES |
|---|
Motivation: Algorithms for phylogenetic tree reconstruction based on gene order data typically repeatedly solve instances of the reversal median problem (RMP) which is to find for three given gene orders a fourth gene order (called median) with a minimal sum of reversal distances. All existing algorithms of this type consider only one median for each RMP instance even when a large number of medians exist. A careful selection of one of the medians might lead to better phylogenetic trees.
Results: We propose a heuristic algorithm amGRP for solving the multiple genome rearrangement problem (MGRP) by repeatedly solving instances of the RMP taking all medians into account. Algorithm amGRP uses a branch-and-bound method that branches over medians from a selected subset of all medians for each RMP instance. Different heuristics for selecting the subsets have been investigated. To show that the medians for RMP vary strongly with respect to different properties that are likely to be relevant for phylogenetic tree reconstruction, the set of all medians has been investigated for artificial datasets and mitochondrial DNA (mtDNA) gene orders. Phylogenetic trees have been computed for a large set of randomly generated gene orders and two sets of mtDNA gene order data for different animal taxa with amGRP and with two standard approaches for solving the MGRP (GRAPPA-DCM and MGR). The results show that amGRP outperforms both other methods with respect to solution quality and computation time on the test data.
Availability: The source code of amGRP, additional results and the test instances used in this paper are freely available from the authors.
Contact: merkle{at}informatik.uni-leipzig.de
|
1 INTRODUCTION |
|---|
|
TOPABSTRACT1 INTRODUCTION2 BASIC DEFINITIONS3 INFERRING PHYLOGENETIC TREES4 GRAPPA AND MGR5 ALGORITHM amGRP6 EXPERIMENTS7 CONCLUSIONREFERENCES |
|---|
The order of genes in the genome of a species changes during evolution due to gene rearrangement mutations. Hence, the differences between the gene order in the genome of different species can be used to infer information on their evolutionary relationships. A common method to compare the gene order of two species is to compute a sequence of genome rearrangement operations that transfers one order into the other. Of particular interest are most parsimonious rearrangement scenarios which use a minimal number of rearrangement operations. Formally, gene orders can be described as signed permutations over a set of integers where each integer denotes a gene and its sign denotes the orientation. The most often considered rearrangement operations are reversal operations (reversals) which are permutations that reverse the order of a subsequence of neighboured genes and change the sign of each reversed gene. The minimal number of reversals that are required to convert one given signed permutation into another given signed permutation is called reversal distance (Sankoff et al., 1996) and can be used to measure the phylogenetic distance between species. The reversal distance between two signed permutations can be calculated in linear time (Bader et al., 2001).
An important problem is to find the most parsimonious rearrangement scenario for multiple genomes. Given a set of gene orders of length n the multiple genome rearrangement problem (MGRP) is to find a tree which has the given gene orders as leaves and an assignment of gene orders of length n to the inner nodes of the tree such that the sum over the reversal distances between the two nodes of every edge is minimal. An important subproblem of MGRP is the case of three given gene orders. This problem is called reversal median problem (RMP). Caprara (2003) has shown that RMP is NP-complete.
GRAPPA (Moret et al., 2001; 2004) and MGR (Bourque and Pevzner, 2002) are two well-known approaches for solving the MGRP. A key element of GRAPPA and MGR is an algorithm for solving the RMP. GRAPPA has integrated two different branch-and-bound algorithms for RMP—Siepel's median solver (Moret and Siepel, 2001) and Caprara's median solver (Caprara, 2003). MGR uses heuristic methods to solve the RMP. Another heuristic for the RMP—called rEvoluzer (Bernt et al., 2005)—differs from GRAPPA and MGR in the sense that it tries to find a rearrangement scenario that does not destroy conserved intervals. [This combinatorial structure for describing gene groups was introduced by Bergeron and Stoye (2003).]
All existing algorithms that solve the MGRP via the RMP consider only one median for each RMP instance even when a large number of medians might exist that could lead to better phylogenetic trees. In this paper we develop an algorithm called amGRP for the MGRP that takes all medians for each RMP instance into account. The general idea is to use a branch-and-bound method that branches over these medians. Instead of branching over all medians this is done only over a subset of all medians. Different heuristics for selecting these subsets are investigated. Algorithm amGRP is tested on a large set of random data and a set of mitochondrial DNA (mtDNA) gene order data for different animal taxa. The results of amGRP are compared with two standard approaches for solving the MGRP (GRAPPA-DCM and MGR). The results show that amGRP outperforms both other methods with respect to solution quality and computation time on the test data.
To motivate that our algorithm considers more than just one median for each RMP instance we have investigated the variance of some properties of all medians for artificial datasets and gene orders from mtDNA.
In Section 2 we give basic definitions. Section 3 briefly presents methods for phylogenetic tree reconstruction based on gene order data. Two well-known parsimony-based methods—GRAPPA and MGR—are explained in Section 4. Algorithm amGRP is introduced in Section 5, and experimental results are discussed in Section 6. Conclusions are drawn in Section 7.
|
2 BASIC DEFINITIONS |
|---|
|
TOPABSTRACT1 INTRODUCTION2 BASIC DEFINITIONS3 INFERRING PHYLOGENETIC TREES4 GRAPPA AND MGR5 ALGORITHM amGRP6 EXPERIMENTS7 CONCLUSIONREFERENCES |
|---|
A permutation of length n is a permutation of {1,2, ... , n}. It is a signed permutation if every element has an additional sign ‘+’ or ‘–’ that defines its orientation (the ‘+’ sign is usually omitted). In the rest of the paper we call a signed permutation shortly a permutation. A ‘reversal’
(i,j), 1 
i j n applied to a signed permutation 
of length n transforms it into the signed permutation 
= (1, ... , i–1, –j, ... , –i, j+1,...n). The ‘reversal distance’ d(,
) between two signed permutations and is the minimum number of reversals that is necessary to transform into . For three given signed permutations 1, 2, 3 define the ‘circumference’ 
, and the ‘sum of pairwise distance differences (spd-value)’ 
Formally, the MGRP is to find for given m (signed) permutations 1, ... , m of length n a tree T where the nodes are (signed) permutations and the leaves are the given permutations, such that the ‘score’
 |
1, 2, 3) for RMP was shown by Moret and Siepel (2001). |
3 INFERRING PHYLOGENETIC TREES |
|---|
|
TOPABSTRACT1 INTRODUCTION2 BASIC DEFINITIONS3 INFERRING PHYLOGENETIC TREES4 GRAPPA AND MGR5 ALGORITHM amGRP6 EXPERIMENTS7 CONCLUSIONREFERENCES |
|---|
Methods for phylogenetic reconstruction can be divided into three classes: distance-based methods, parsimony-based methods and likelihood-based methods. Distance-based methods use the pairwise distance between gene orders to determine evolutionary relationship, likelihood methods attempt to reconstruct a phylogeny using an explicit model of evolution, and parsimony methods try to find a tree with a minimal number of evolutionary changes (Felsenstein, 2004). In parsimony-based methods ancestral data have to be reconstructed. Finding the most parsimonious tree is computationally very expensive, as (1) there exist (2m – 5)!! different tree topologies with m leaves (the double factorial denotes the fact that only every odd factor is used) and (2) even solving the median problem for three input gene orders is NP-complete. Two standard parsimony algorithms are described in Section 4.
|
4 GRAPPA AND MGR |
|---|
|
TOPABSTRACT1 INTRODUCTION2 BASIC DEFINITIONS3 INFERRING PHYLOGENETIC TREES4 GRAPPA AND MGR5 ALGORITHM amGRP6 EXPERIMENTS7 CONCLUSIONREFERENCES |
|---|
GRAPPA and MGR are two state-of-the-art parsimony-based approaches to find good phylogenetic reconstructions for gene order data within reasonable amount of computation time.
MGR (Bourque and Pevzner, 2002) is based on heuristics to solve the RMP. For three given permutations 1, 2, 3 it iteratively tries to identify a reversal that brings one of the permutations closer to the other two permutations. Because it is possible that there exist more than one such reversal, or no such reversal exists, several heuristics and a look-ahead strategy are available to identify a promising candidate reversal. The putative median is the permutation where two permutations meet. To solve the RMP the algorithm starts to identify reversals which bring one permutation closer to all other permutations. If no such reversal exists, the algorithm connects the unconnected permutations by using the MGR-median solver. This is done by a greedy identification of triples for which splitting an edge according to a sequential addition should lead to a minimal number of additional reversals. For the chosen triple the RMP is solved.
GRAPPA [for details see Moret et al. (2001, 2004)] iterates over all possible tree topologies. For each topology, GRAPPA first initializes the internal nodes. Then, for each internal node a median µ of its three neighbours 1, 2, 3 is computed, and is replaced by µ if this improves the score of the tree. This is repeated until no internal node can be relabelled. GRAPPA provides several methods to solve the occurring median problems, with Siepel's median solver (Moret and Siepel, 2001) and Caprara's median solver (Caprara, 2003) being the most important algorithms. Both approaches are branch-and-bound algorithms which solve the problem to optimality. Caprara's median solver is the recommended method (personal communication with J. Tang). GRAPPA cannot solve datasets with more than 13 given gene orders in reasonable time because the number of tree topologies gets too large. Therefore in (16) GRAPPA was adapted to work with the disk covering method (DCM) (Huson et al., 1999). DCM decomposes the given dataset into smaller subsets, the disks. These datasets are then independently solved (here by GRAPPA) and afterwards reconnected by the DCM method.
Note, that neither GRAPPA nor MGR guarantees to return optimal solutions for the MGRP. In algorithm MGR the median problems as well as the tree reconstruction are solved heuristically. GRAPPA does not return optimal solutions although it iterates over all possible tree topologies and solves each median problem optimal. This is because it cannot assign the labels of the internal nodes in an optimal way.
|
5 ALGORITHM amGRP |
|---|
|
TOPABSTRACT1 INTRODUCTION2 BASIC DEFINITIONS3 INFERRING PHYLOGENETIC TREES4 GRAPPA AND MGR5 ALGORITHM amGRP6 EXPERIMENTS7 CONCLUSIONREFERENCES |
|---|
5.1 Sequential addition
Algorithm amGRP is based on sequential addition (Felsenstein, 2004). In a sequential addition-based algorithm edges are iteratively added to a partially reconstructed tree. For adding a permutation to a partially reconstructed tree one edge is removed (the split edge), and the nodes of the split edge have to be connected to the permutation. One step of sequential addition is depicted in Figure 1, where the split edge e is removed, and the median problem for permutations
1, 2, 3 is solved. The median µ is directly connected to the other permutations. Note, that in algorithm amGRP the selected medians which are processed iteratively in the branching step are chosen according to certain criteria (cf. Section 5.2) from the set of all medians.
|
Algorithm 1: amGRP
Algorithm amGRP is a depth first search algorithm where a partial phylogeny that contains k + 2 gene orders corresponds to a node in a search tree at level k, k 
1. The pseudo-code is given in Algorithm 1. Given m permutations 1,...m; all possible m · (m – 1) · (m – 2) triples of these permutations are sorted according to their lower bound in a list denoted by C. Then the median problem is solved for each triple considering triples in order of increasing lower bound. If the median score of the considered triple is lower than or equal to the best median score found so far, the triple is added to a set T. If the median score of the considered triple is less than the best median score found so far, T is reinitialized and the triple is added to T. If the lower bound of the considered triple is larger then the best median score found the process is stopped, as no better median solution can be found. After this step set T contains all triples with the best median score. If set T has to be computed when a partial tree already exists, then C includes all possible triples where two permutations are the nodes of an edge (the split edge) of the partial tree, and the third permutation is an unconnected permutation. After T has been computed for every triple in T all medians for each triple in T are computed, as we only computed one median so far. This is done optimally with Caprara's median solver in GRAPPA. As the median score has already been determined it can be used as upper and lower bound for Caprara's branch-and-bound median solver to reduce the execution time. In the branching step for each triple and each median a sequential addition step is performed. The split edge is removed, and the three nodes are connected to the median. Using this partial phylogeny, the recursion of the algorithm is done, until no unconnected permutations are left.
5.2 Median selection
Since the number of possible tree topologies for m gene orders is (2m – 5)!!, several strategies to reduce the running time are applied. First, the branching is not done over all possible medians but only over selected medians with certain properties. The following selection methods for the medians have been used:
- Compute for each median the sum of the reversal distances to the unconnected nodes. Select all medians for which the sum of these distances is minimal (nearest).
- Compute for all medians the length of the longest edge in the median solution. Select all medians for which the longest edge has a maximal value (longest).
- Compute for all medians the length of the shortest edge in the median solution. Select all medians for which the shortest edge has a minimal value (shortest).
- Compute for all medians the skewness, i.e. the difference of the length of the longest and shortest edge in the median solution. Select all medians for which this value is maximal (skewest).
- Select a random median (random).
5.3 Lower bounds and sampling
To further reduce the execution time of algorithm amGRP lower bounds on the solution quality are used. A strategy that is always applied is to discard an upcoming branching step if the score of the complete solution that incorporates a given partial solution cannot improve the best solution found so far (std LB). Note, that branching over all triples of all best medians does not guarantee the optimality of the solution for the MGR problem (Felsenstein, 2004). Another more restrictive lower bound strategy uses a lower bound per level of the search tree and discards a branching step, if the considered partial solution exceeds the lower bound at that level (level LB), i.e. a branching step is only done if the score of the partial solution is at least as good as the best partial solution found so far on the current branching level.
If algorithm amGRP using strategy std LB is executed until all branches are processed, amGRP is a standard branch-and-bound algorithm. When phylogenies for many gene orders have to be found and the processing of all branches is practically impossible, algorithm amGRP is executed as a sampling method (not shown in the pseudo-code of amGRP) which uses an elaborated median selection. Then not all branches but only one out of all best branches is selected randomly, and the algorithm stops if all gene orders are connected to a tree. This process is iterated, until a maximal number of sampled trees is generated. The maximal number of sampled trees has to be used as a parameter for algorithm amGRP.
|
6 EXPERIMENTS |
|---|
|
TOPABSTRACT1 INTRODUCTION2 BASIC DEFINITIONS3 INFERRING PHYLOGENETIC TREES4 GRAPPA AND MGR5 ALGORITHM amGRP6 EXPERIMENTS7 CONCLUSIONREFERENCES |
|---|
In this section we investigate the sets of medians for artificial datasets and gene orders of mtDNA. Phylogenetic trees have been computed for a large set of randomly generated gene orders and two sets of mtDNA gene order data for different animal taxa with amGRP and with two standard algorithms. Results using different median selection methods for reconstructing phylogenetic trees are presented. All test runs were performed on a standard 2 GHz PC.
6.1 Properties of the median set
To investigate the properties of median sets we used artificial datasets and biological datasets as input permutations and solved the median problem for all possible triples for each input dataset. Note, that there exist 
, n > 1 different instances (with pairwise different permutations) for the median problem for gene orders of length n, which makes a complete enumeration of all medians for all median problems for permutations of length >5 practically impossible. Note, that when possible triples of a given length are sampled, it is very likely that for one random instance the pairwise distance of the permutations is very close to the maximum, which is not the case for biological datasets.
Let G be a median graph for three given input permutations. Then each node in G corresponds to a permutation which is a solution for the median problem. Two nodes in G are connected, if there is a reversal that transforms one permutation into the other. We investigated for all triples in both datasets the number of instances, the score, the number of medians and the diameter (the maximal shortest reversal distance between two medians). These results are given as average values for all classes of instances depending on the circumference and the spd-value of the triple.
6.1.1 Artificial datasets
All 7.37 million possible input triples for three permutations of length n = 5 have been generated, and for all instances all medians have been computed. The instances have been classified according to the circumference and the spd-value of the input triple. Figure 2 depicts (1) the number of instances, (2) the average score, (3) the average number of medians and (4) the diameter of the set of medians for all possible classes. It is easy to see, that even for very short input permutations the number of possible medians can be large. The maximal average number of median per class is 8.23. Also the diameter results for connected components and the number of connected components (not presented) of the median graph show the potential of using not only one median but also an elaborated selection from the set of all medians for phylogenetic reconstruction.
|
6.1.2 Biological datasets
For the biological datasets we took all mitochondrial genomes that were marked as complete from the Mitochondrial Database (Boore, 2005). From these mitochondrial gene orders we selected all those gene orders that contain all the 37 standard genes that can be found in animal mitochondrial genomes. These standard genes are (1) 13 protein coding genes cox1, cox2, cox3, nad1, nad2, nad3, nad4, nad4L, nad5, nad6, atp6, atp8 and cob, (2) 2 rRNA genes rrnL and rrnS and (3) 22 tRNA genes L(nag), Y, A, V, E, D, G, F, I, H, K, M, Q, P, R, W, S(nct), N, L(yaa), C, S(nga) and T. The species of the resulting mitochondrial gene orders were grouped into taxa with the help of taxonomy information in the Mitochondrial Database and manual inspection of the phylogenetic tree given from the NCBI taxonomy browser. For all taxa we generated all possible triples for each group of taxa (resulting in 31 805 triples) and calculated all median sets. The results are depicted in Figure 3. Similar to the results for permutations of length n = 5, this results also show the potential of the usage of a median set. The average number of medians per class was 48.13 and for 147 out of 1107 possible classes the average number of medians was larger than 100 (cf. Fig. 3). Also for the biological dataset the median graph is very irregular in the sense that the maximal shortest reversal distance between components of G can be large (up to 11) and the median graph has many components of very different size. In Figure 3 it is obvious that most of the biological permutations of the triple instances are relatively close. The sum of circumference and spd-value is <100 for 29 926 of all instances. There is a clear separation of those triple instances and the rest of the instances. A further investigation showed that the reason for this separation are the three arthropods Heterodoxus macropus, Leptotrombidium akamushi and Tigriopus japonicus and the large evolutionary distance of the molluscs. This result is in correspondence with published results, like (Shao et al., 2001), where it was shown that the large number of gene rearrangements in the mt genome of H.macropus is unprecedented for an arthropod. Removing the molluscs and the three mentioned arthropod gene orders would result in a dataset with no instances in the classes for which the sum of circumference and spd-value is >100.
|
6.2 Phylogenetic trees
We used GRAPPA (using DCM for the random datasets with m = 50 and for the protostome dataset), MGR (using heuristic parameter options 3 and 5 as suggested by Guillaume Bourque) and amGRP to infer phylogenetic trees. Again, we investigated the algorithms on random datasets and on biological datasets.
6.2.1 Random datasets
For the random datasets input permutations for the MGR problem according to the method proposed in (Moret et al., 2004) were generated. First, 100 random tree topologies were generated with m = 50 nodes according to the well-known Markovian (Yule process) model. Then, the identity permutation is assigned to the root of each tree and r random reversals were performed on each edge, resulting in m permutations. These 100 datasets were taken as input permutations for GRAPPA, MGR and amGRP. Figure 4 depicts the achieved scores and the execution time for gene orders of length n = 50 and r 
{4,6,8} reversals per edge. The same was done for m = 10 (results are omitted due to space limitations). For algorithm amGRP all five median selection strategies presented in Section 5.2 were investigated. For each variant of amGRP a sampling size of 10 was used, i.e. amGRP was allowed to generate 10 phylogenies for each input dataset, and the best result was taken. In each of the subfigures a boxplot for the score of the resulting tree and the runtime is presented for amGRP-random, amGRP-skewest, amGRP-longest, amGRP-shortest, amGRP-nearest, MGR with heuristic 3, MGR with heuristic 5 and GRAPPA using DCM with a disk size of 10. Algorithm amGRP always performs significantly better than MGR, only for r = 4 GRAPPA was able to achieve better scores but using much more computation time (note the logarithmic scale in the subfigures depicting computation times). For r = 8 GRAPPA was able to solve only 5 out of 100 instances with a time limitation of 10 000 s per instance. This time limitation was chosen because the first two instances could not be solved within one day each. The five solutions (seven trees) found were significantly worse with respect to score (score difference always >10) and Robinson–Foulds (RF) distance (see next paragraph). Although the differences of the median selection strategies are only small, we conclude that for the given sets of gene orders strategies ‘skewest’ and ‘nearest’ perform best.
|
For the random datasets we also computed the RF distance between the originating and the resulting trees. Results are presented in Figure 5. Note, that the outcome of an algorithm can be more than one tree with the same score. Therefore, the average number of RF distances is not based on 100 tree distances, but usually more. The average RF distance achieved by algorithm amGRP is always smaller than that for GRAPPA and MGR. Clearly amGRP outperforms GRAPPA and MGR.
|
6.2.2 Biological datasets
Here we present results for a metazoan [used before in Bourque and Pevzner (2002) and Blanchette et al. (1999), m = 11 gene orders of length n = 37] and a protostome (Fritzsch et al., 2005) mtDNA dataset. From the protostome dataset we removed duplicates and gene atp8 resulting in m = 62 gene orders of length n = 36 (atp8 was removed because otherwise too many species would have been discarded). Note, that for metazoan mtDNA a tree reconstruction with 150 reversals was published in Bourque and Pevzner (2002) showing that the MGR outperforms GRAPPA for this dataset, as GRAPPA needs more than 48 h to find a solution with 175 reversals. We used algorithm amGRP with a sampling size of 500. The boxplots for the result are given in Figure 6. Algorithm amGRP-longest was able to find a solution with score 142, the worst strategy leads to a score of 148. The computation time per sample was only 19.7 s on average. For the metazoan mtDNA dataset algorithm amGRP without using a median selection strategy and using the bounding method level LB was able to traverse the complete search tree and found a solution with score 142 in 115 min computation time. Using amGRP-skewest and bounding method level LB the complete search tree was traversed in 18 min computation time and a solution with score 144 was found. GRAPPA was not able to find a solution better than score 147 in
4.5 months computation time. For the protostome mtDNA gene orders MGR was able to find a solution with score 525 in 37 min and 18 s, GRAPPA was not able to find any solution (we tested GRAPPA combined with DCM and disk sizes of 3–14, each test run had a maximal computation time of 2 days). The best score of 498 was found with algorithms amGRP-longest and amGRP-skewest. The average time for sampling one solution with amGRP was 360.4 s on average.
|
|
7 CONCLUSION |
|---|
|
TOPABSTRACT1 INTRODUCTION2 BASIC DEFINITIONS3 INFERRING PHYLOGENETIC TREES4 GRAPPA AND MGR5 ALGORITHM amGRP6 EXPERIMENTS7 CONCLUSIONREFERENCES |
|---|
A key element for phylogenetic reconstruction with parsimony-based algorithms based on the reversal distance of gene orders is solving the reversal median problem. Considering not only one but all medians when solving an instance of this problem could lead to better phylogenetic trees. Therefore, median graphs have been investigated for artificial and biological datasets. It was shown that the medians have very different properties and therefore it is seems profitable to incorporate heuristics for selection of the most suitable medians into methods for inferring phylogenies. Based on these results we proposed a new method for parsimony-based tree reconstruction for gene order datasets. In contrast to other approaches, like MGR or GRAPPA, algorithm amGRP selects elements from the set of all medians that have certain properties. We have shown that algorithm amGRP clearly outperforms GRAPPA and MGR both with respect to the score and with respect to computation time. This was shown using random datasets and mtDNA gene orders. For metazoan and protostomes gene orders we were able to find phylogenies with scores which could not be found by any other approach. In our future research we will apply consensus tree methods that use the resulting trees of amGRP as input trees.
|
Acknowledgments |
|---|
This work was supported by the German Research Foundation (DFG) through the project ‘Deep Metazoan Phylogeny’ within SPP 1174. The authors wish to thank Guido Fritzsch and Peter Stadler for their very helpful comments. We thank Jijun Tang for providing GRAPPA-DCM and his immediate response when we had questions. We thank Guillaume Bourque for providing MGR and his help on finding the best parameters for the MGR test runs.
|
REFERENCES |
|---|
|
TOPABSTRACT1 INTRODUCTION2 BASIC DEFINITIONS3 INFERRING PHYLOGENETIC TREES4 GRAPPA AND MGR5 ALGORITHM amGRP6 EXPERIMENTS7 CONCLUSIONREFERENCES |
|---|
Bader, D.A., et al. (2001) A linear-time algorithm for computing inversion distances between signed permutations with an experimental study. J. Comput. Biol, . 8, 483–491[CrossRef][Web of Science][Medline].
Bernt, M., Merkle, D., Middendorf, M. (2005) Genome rearrangement based on reversals that preserve conserved intervals. IEEE/ACM Trans. on Comp. Biol. and Bioinformatics, (to appear).
Bergeron, A. and Stoye, J. (2003) On the similarity of sets of permutations and its applications to genome comparison. Proceedings of the COCOON-2003, pp. 68–79 Springer: LNCS 2697.
Blanchette, M., et al. (1999) Gene order breakpoint evidence in animal mitochondrial phylogeny. J. Mol. Evol, . 49, 193–203[CrossRef][Web of Science][Medline].
Boore, J.L. (2005) Mitochondrial database. http://evogen.jgi.doe.gov/.
Bourque, G. and Pevzner, P.A. (2002) Genome-scale evolution: reconstructing gene orders in the ancestral species. Genome Res, . 12, 26–36
Caprara, A. (2003) The reversal median problem. INFORMS J. Comput, . 15, 93–113.
Felsenstein, J. (2004) Inferring Phylogenies. , Sunderland, MA Sinauer Associates.
Fritzsch, G., et al. (2005) Alignments of mitochondrial genome arrangements: applications to metazoan phylogeny. J. Theor. Biol, . 240, 511–520.
Huson, D., et al. (1999) Disk-covering, a fast converging method for phylogenetic tree reconstruction. J. Comput. Biol, . 6, 369–386[CrossRef][Web of Science][Medline].
Moret, B., et al. (2004) Reconstructing phylogenies from gene-content and gene-order data. Math. Evol. Phylog, ., pp. 321–352.
Moret, B. and Siepel, A. (2001) Finding an optimal inversion median: experimental results. Proceedings of the WABI-2001.Springer: LNCS 2149, pp. , pp. 189–203.
Moret, B., et al. (2001) New approaches for reconstructing phylogenies from gene order data. Proc. Int. Conf. Intell. Syst. Mol. Biol. (ISMB-2001), , pp. 165–173.
Sankoff, D. (1992) Edit distance for genome comparison based on non-local operations. Proceedings of the CPMSpringer: LNCS 644, pp. , pp. 121–135.
Sankoff, D., et al. (1996) Steiner points in the space of genome rearrangements. Int. J. Found. Comput. Sci, . 8, 1–9.
Shao, R., et al. (2001) Numerous Gene Rearrangements in the Mitochondrial Genome of the Wallaby Louse, Heterodoxus macropus (Phthiraptera). Mol. Biol. Evol, . 18, 858–865
Tang, J. and Moret, B. (2003) Scaling up accurate phylogenetic reconstruction from gene-order data. Proc. Int. Conf. Intell. Syst. Mol. Biol. (ISMB-2003), 19, 305–312.
CiteULike 
Connotea 
Del.icio.us What's this?
This article has been cited by other articles:
|
|
 |
|
  M. Bernt, D. Merkle, K. Ramsch, G. Fritzsch, M. Perseke, D. Bernhard, M. Schlegel, P. F. Stadler, and M. Middendorf CREx: inferring genomic rearrangements based on common intervals Bioinformatics, November 1, 2007; 23(21): 2957 - 2958. [Abstract] [Full Text] [PDF]
|
|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||