Preserving Inversion Phylogeny Reconstruction

详细信息    查看全文

• 作者：Matthias Bernt (21)
  Kun-Mao Chao (22)
  Jyun-Wei Kao (22)
  Martin Middendorf (21)
  Eric Tannier (23)
  
• 刊名：Lecture Notes in Computer Science
• 出版年：2012
• 出版时间：2012
• 年：2012
• 卷：7534
• 期：1
• 页码：14-29
• 全文大小：275KB
• 参考文献：1. Belda, E., Moya, A., Silva, F.J.: Genome rearrangement distances and gene order phylogeny in / γ-proteobacteria. Mol. Biol. Evol.?22, 1456-467 (2005) CrossRef
  2. Bérard, S., Bergeron, A., Chauve, C., Paul, C.: Perfect sorting by reversals is not always difficult. IEEE/ACM Trans. Comput. Biol. Bioinf.?4, 4-6 (2007) CrossRef
  3. Bérard, S., Chauve, C., Paul, C.: A more efficient algorithm for perfect sorting by reversals. Inform. Process. Lett.?106, 90-5 (2008) CrossRef
  4. Bergeron, A., Chauve, C., de Montgolfier, F., Raffinot, M.: Computing common intervals of / k permutations, with applications to modular decomposition of graphs. SIAM J. Discrete Math.?22, 1022-039 (2008) CrossRef
  5. Bernt, M.: Gene Order Rearrangement Methods for the Reconstruction of Phylogeny. PhD thesis, Universit?t Leipzig (2010)
  6. Bernt, M., Merkle, D., Middendorf, M.: Solving the preserving reversal median problem. IEEE/ACM Trans. Comput. Biol. Bioinf.?5, 332-47 (2008) CrossRef
  7. Bernt, M., Merkle, D., Ramsch, K., Fritzsch, G., Perseke, M., Bernhard, D., Schlegel, M., Stadler, P.F., Middendorf, M.: CREx: inferring genomic rearrangements based on common intervals. Bioinformatics?23, 2957-958 (2007) CrossRef
  8. Booth, K., Lueker, G.: Testing for the consecutive ones property, interval graphs and graph planarity using PQ-tree algorithms. J. Comput. Syst. Sci.?13, 335-39 (1976) CrossRef
  9. Bouvel, M., Chauve, C., Mishna, M., Rossin, D.: Average-Case Analysis of Perfect Sorting by Reversals. In: Kucherov, G., Ukkonen, E. (eds.) CPM 2009. LNCS, vol.?5577, pp. 314-25. Springer, Heidelberg (2009) CrossRef
  10. Day, W.H.E., Sankoff, D.: Computational complexity of inferring phylogenies by compatibility. Syst. Zool.?35, 224-29 (1986) CrossRef
  11. Dutheil, J., Gaillard, S., Bazin, E., Glemin, S., Ranwez, V., Galtier, N., Belkhir, K.: Bio++: a set of C++ libraries for sequence analysis, phylogenetics, molecular evolution and population genetics. BMC Bioinformatics?7(1), 188 (2006) CrossRef
  12. Feijao, P., Meidanis, J.: SCJ: A breakpoint-like distance that simplifies several rearrangement problems. IEEE/ACM Trans. Comput. Biol. Bioinf.?8, 1318-329 (2011) CrossRef
  13. Fertin, G., Labarre, A., Rusu, I., Tannier, E., Vialette, S.: Combinatorics of Genome Rearrangements. MIT Press (2009)
  14. Figeac, M., Varré, J.-S.: Sorting by Reversals with Common Intervals. In: Jonassen, I., Kim, J. (eds.) WABI 2004. LNCS (LNBI), vol.?3240, pp. 26-7. Springer, Heidelberg (2004) CrossRef
  15. Fitch, W.: Toward defining the course of evolution: minimum change for a specified tree topology. Syst. Zool.?20, 406-16 (1971) CrossRef
  16. Foulds, L.R., Graham, R.L.: The Steiner problem in phylogeny is NP-complete. Adv. Appl. Math.?3, 43-9 (1982) CrossRef
  17. Hannenhalli, S., Pevzner, P.A.: Transforming cabbage into turnip: polynomial algorithm for sorting signed permutations by reversals. In: ACM Symposium on Theory of Computing, pp. 178-89 (1995)
  18. Heber, S., Stoye, J.: Finding All Common Intervals of / k Permutations. In: Amir, A., Landau, G.M. (eds.) CPM 2001. LNCS, vol.?2089, pp. 207-18. Springer, Heidelberg (2001) CrossRef
  19. Penel, S., Arigon, A.M., Dufayard, J.F., Sertier, A.S., Daubin, V., Duret, L., Gouy, M., Perrière, G.: Databases of homologous gene families for comparative genomics. BMC Bioinformatics?10, S3 (2009) CrossRef
  20. Sankoff, D.: Edit Distance for Genome Comparison Based on Non-Local Operations. In: Apostolico, A., Galil, Z., Manber, U., Crochemore, M. (eds.) CPM 1992. LNCS, vol.?644, pp. 121-35. Springer, Heidelberg (1992) CrossRef
  21. Tannier, E., Zheng, C., Sankoff, D.: Multichromosomal median and halving problems under different genomic distances. BMC Bioinformatics?10, 120 (2009) CrossRef
  
• 作者单位：Matthias Bernt (21)
  Kun-Mao Chao (22)
  Jyun-Wei Kao (22)
  Martin Middendorf (21)
  Eric Tannier (23)
  
  21. Parallel Computing and Complex Systems Group, Institute of Computer Science, University Leipzig, Germany
  22. Department of Computer Science and Information Engineering, National Taiwan University, Taiwan
  23. INRIA Rh?ne-Alpes; UMR CNRS 5558 “Biométrie et Biologie évolutive- Université de Lyon 1, Villeurbanne, France
  

文摘

Tractability results are rare in the comparison of gene orders for more than two genomes. Here we present a linear-time algorithm for the small parsimony problem (inferring ancestral genomes given a phylogeny on an arbitrary number of genomes) in the case gene orders are permutations, that evolve by inversions not breaking common gene intervals, and these intervals are organised in a linear structure. We present two examples where this allows to reconstruct the ancestral gene orders in phylogenies of several γ-Proteobacteria species and Burkholderia strains, respectively. We prove in addition that the large parsimony problem (where the phylogeny is output) remains NP-complete.