Common Intervals of Multiple Permutations

1. Heber, S., Stoye, J.: Algorithms for finding gene clusters. In: Proceedings of the First International Workshop on Algorithms in Bioinformatics (WABI 2001). Lecture Notes in Computer Science, vol. 2149, pp. 252–263. Springer, Berlin (2001)

   Google Scholar 

2. Heber, S., Stoye, J.: Finding all common intervals of k permutations. In: Proceedings of the 12th Annual Symposium on Combinatorial Pattern Matching (CPM 2001). Lecture Notes in Computer Science, vol. 2089, pp. 207–218. Springer, Berlin (2001)

   Chapter  Google Scholar 

3. Marcotte, E.M., Pellegrini, M., Ng, H.L., Rice, D.W., Yeates, T.O., Eisenberg, D.: Detecting protein function and protein-protein interactions from genome sequences. Science 285, 751–753 (1999)

   Article  Google Scholar 

4. Overbeek, R., Fonstein, M., D’Souza, M., Pusch, G.D., Maltsev, N.: The use of gene clusters to infer functional coupling. Proc. Natl. Acad. Sci. USA 96, 2896–2901 (1999)

   Article  Google Scholar 

5. Snel, B., Lehmann, G., Bork, P., Huynen, M.A.: STRING: A web-server to retrieve and display the repeatedly occurring neigbourhood of a gene. Nucleic Acids Res. 28, 3443–3444 (2000)

   Article  Google Scholar 

6. Bergeron, A., Heber, S., Stoye, J.: Common intervals and sorting by reversals: A marriage of necessity. In: Proceedings of the European Conference on Computational Biology (ECCB 2002) (Supplement of Bioinformatics), vol. 18, pp. 54–63. University Press, Oxford (2002) (Suppl. 2)

   Google Scholar 

7. Bergeron, A., Stoye, J.: On the similarity of sets of permutations and its applications to genome comparison. In: Proceedings of the 9th International Computing and Combinatorics Conference, COCOON 2003. Lecture Notes in Computer Science, vol. 2697, pp. 68–79. Springer, Berlin (2003)

   Google Scholar 

8. Brady, R.M.: Optimization strategies gleaned from biological evolution. Nature 317, 804–806 (1985)

   Article  Google Scholar 

9. Kobayashi, S., Ono, I., Yamamura, M.: An efficient genetic algorithm for job shop scheduling problems. In: Proceedings of the 6th International Conference on Genetic Algorithms, pp. 506–511. Morgan Kaufmann, San Francisco (1995)

   Google Scholar 

10. Mühlenbein, H., Gorges-Schleuter, M., Krämer, O.: Evolution algorithms in combinatorial optimization. Parallel Comput. 7, 65–85 (1988)

    Article  MATH  Google Scholar 

11. Bergeron, A., Chauve, C., de Montgolfier, F., Raffinot, M.: Computing common intervals of K permutations, with applications to modular decomposition of graphs. In: Proceedings of the 13th Annual European Symposium on Algorithms, ESA 2005. Lecture Notes in Computer Science, vol. 3669, pp. 779–790. Springer, Berlin (2005)

    Google Scholar 

12. Heber, S., Savage, C.: Common intervals of trees. Inf. Process. Lett. 93, 69–74 (2005)

    Article  MATH  MathSciNet  Google Scholar 

13. Booth, K.S., Lueker, G.S.: Testing for the consecutive ones property, interval graphs and graph planarity using PQ-tree algorithms. J. Comput. Syst. Sci. 13, 335–379 (1976)

    Article  MATH  MathSciNet  Google Scholar 

14. Fulkerson, D., Gross, O.: Incidence matrices with the consecutive 1s property. Bull. Am. Math. Soc. 70, 681–684 (1964)

    Article  MATH  MathSciNet  Google Scholar 

15. Golumbic, C.: Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York (1990)

    Google Scholar 

16. Uno, T., Yagiura, M.: Fast algorithms to enumerate all common intervals of two permutations. Algorithmica 26, 290–309 (2000)

    Article  MATH  MathSciNet  Google Scholar 

Download references