Cactus Graphs for Genome Comparisons

1. Miller, W., Rosenbloom, K., Hardison, R.C., Hou, M., Taylor, J., Raney, B., Burhans, R., King, D.C., Baertsch, R., Blankenberg, D., Pond, S.L.K., Nekrutenko, A., Giardine, B., Harris, R.S., Tyekucheva, S., Diekhans, M., Pringle, T.H., Murphy, W.J., Lesk, A., Weinstock, G.M., Lindblad-Toh, K., Gibbs, R.A., Lander, E.S., Siepel, A., Haussler, D., Kent, W.J.: 28-way vertebrate alignment and conservation track in the ucsc genome browser. Genome Res. 17(12), 1797–1808 (2007)

   Article  Google Scholar 

2. Paten, B., Herrero, J., Beal, K., Fitzgerald, S., Birney, E.: Enredo and pecan: Genome-wide mammalian consistency-based multiple alignment with paralogs. Genome Res. 18(11), 1814–1828 (2008)

   Article  Google Scholar 

3. Carver, T., Thomson, N., Bleasby, A., Berriman, M., Parkhill, J.: Dnaplotter: circular and linear interactive genome visualization. Bioinformatics 25(1), 119–120 (2009)

   Article  Google Scholar 

4. Krzywinski, M., Schein, J., Birol, I., Connors, J., Gascoyne, R., Horsman, D., Jones, S.J., Marra, M.A.: Circos: an information aesthetic for comparative genomics. Genome Research 19(9), 1639–1645 (2009)

   Article  Google Scholar 

5. Diskin, S.J., Hou, C., Glessner, J.T., Attiyeh, E.F., Laudenslager, M., Bosse, K., Cole, K., Mossé, Y.P., Wood, A., Lynch, J.E., Pecor, K., Diamond, M., Winter, C., Wang, K., Kim, C., Geiger, E.A., McGrady, P.W., Blakemore, A.I.F., London, W.B., Shaikh, T.H., Bradfield, J., Grant, S.F.A., Li, H., Devoto, M., Rappaport, E.R., Hakonarson, H., Maris, J.M.: Copy number variation at 1q21.1 associated with neuroblastoma. Nature 459(7249), 987–991 (2009)

   Article  Google Scholar 

6. Bignell, G.R., Santarius, T., Pole, J.C.M., Butler, A.P., Perry, J., Pleasance, E., Greenman, C., Menzies, A., Taylor, S., Edkins, S., Campbell, P., Quail, M., Plumb, B., Matthews, L., McLay, K., Edwards, P.A.W., Rogers, J., Wooster, R., Futreal, P.A., Stratton, M.R.: Architectures of somatic genomic rearrangement in human cancer amplicons at sequence-level resolution. Genome Research 17(9), 1296–1303 (2007)

   Article  Google Scholar 

7. Hampton, O.A., Hollander, P.D., Miller, C.A., Delgado, D.A., Li, J., Coarfa, C., Harris, R.A., Richards, S., Scherer, S.E., Muzny, D.M., Gibbs, R.A., Lee, A.V., Milosavljevic, A.: A sequence-level map of chromosomal breakpoints in the mcf-7 breast cancer cell line yields insights into the evolution of a cancer genome. Genome Research 19(2), 167–177 (2009)

   Article  Google Scholar 

8. Kent, W.J., Baertsch, R., Hinrichs, A., Miller, W., Haussler, D.: Evolution’s cauldron: duplication, deletion, and rearrangement in the mouse and human genomes. Proc. Natl. Acad. Sci. USA 100(20), 11484–11489 (2003)

   Article  Google Scholar 

9. Harary, F., Uhlenbeck, G.: On the number of husimi trees, i. Proceedings of the National Academy of Sciences 39, 315–322 (1953)

   Article  MATH  MathSciNet  Google Scholar 

10. Bergeron, A., Stoye, J.: On the similarity of sets of permutations and its applications to genome comparison. J. Comput. Biol. 13(7), 1340–1354 (2006)

    Article  MathSciNet  Google Scholar 

11. Bergeron, A., Mixtacki, J., Stoye, J.: Reversal distance without hurdles and fortresses. In: Sahinalp, S.C., Muthukrishnan, S.M., Dogrusoz, U. (eds.) CPM 2004. LNCS, vol. 3109, pp. 388–399. Springer, Heidelberg (2004)

    Google Scholar 

12. Korneyenko, N.M.: Combinatorial algorithms on a class of graphs. Discrete Applied Mathematics, 109–111 (1994)

    Google Scholar 

13. Zamazek, B., Zerovnik, J.: Estimating the traffic on weighted cactus networks in linear time. In: Ninth International Conference on Information Visualisation (IV 2005), pp. 536–541 (2005)

    Google Scholar 

14. Ben-Moshe, B., Bhattacharya, B.: Efficient algorithms for the weighted 2-center problem in a cactus graph. In: Deng, X., Du, D.-Z. (eds.) ISAAC 2005. LNCS, vol. 3827, pp. 693–703. Springer, Heidelberg (2005)

    Chapter  Google Scholar 

15. Tetsuo, N.: On the number of solutions of a class of nonlinear resistive circuit. In: Proceedings of the IEEE International Symposium on Circuits and Systems, Singapore, pp. 766–769 (1991)

    Google Scholar 

16. Alekseyev, M.A., Pevzner, P.A.: Breakpoint graphs and ancestral genome reconstructions. Genome Research 19(5), 943–957 (2009)

    Article  Google Scholar 

17. Pevzner, P.A., Tang, H., Waterman, M.S.: An eulerian path approach to dna fragment assembly. Proc. Natl. Acad. Sci. USA 98(17), 9748–9753 (2001)

    Article  MATH  MathSciNet  Google Scholar 

18. Raphael, B., Zhi, D., Tang, H., Pevzner, P.: A novel method for multiple alignment of sequences with repeated and shuffled elements. Genome Res. 14(11), 2336–2346 (2004)

    Article  Google Scholar 

19. Tsin, Y.H.: A simple 3-edge-connected component algorithm. Theory Comput. Syst. 40(2), 125–142 (2007)

    Article  MATH  MathSciNet  Google Scholar 

20. Lunter, G., Rocco, A., Mimouni, N., Heger, A., Caldeira, A., Hein, J.: Uncertainty in homology inferences: assessing and improving genomic sequence alignment. Genome Res. 18(2), 298–309 (2008)

    Article  Google Scholar 

21. ENCODE-Consortium: Identification and analysis of functional elements in 1 genome by the encode pilot project. Nature 447(7146), 799–816 (2007)

    Google Scholar 

Download references