Quadratic Time Algorithms for Finding Common Intervals in Two and More Sequences

Schmidt T, Stoye J (2004)
In: Proc. of CPM 2004. LNCS, 3109. 347-358.

Download
Es wurde kein Volltext hochgeladen. Nur Publikationsnachweis!
Konferenzbeitrag | Veröffentlicht | Englisch
Autor
;
Abstract / Bemerkung
A popular approach in comparative genomics is to locate groups or clusters of orthologous genes in multiple genomes and to postulate functional association between the genes contained in such clusters. To this end, genomes are often represented as permutations of their genes, and common intervals, i.e. intervals containing the same set of genes, are interpreted as gene clusters. A disadvantage of modelling genomes as permutations is that paralogous copies of the same gene inside one genome can not be modelled. In this paper we consider a slightly modified model that allows paralogs, simply by representing genomes as sequences rather than permutations of genes. We define common intervals based on this model, and we present a simple algorithm that finds all common intervals of two sequences in theta(n(2)) time using theta(n(2)) space. Another, more complicated algorithm runs in O(n(2)) time and uses only linear space. We also show how to extend the simple algorithm to more than two genomes, and we present results from the application of our algorithms to real data.
Erscheinungsjahr
Titel des Konferenzbandes
Proc. of CPM 2004
Band
3109
Seite
347-358
Konferenz
CPM 2004
Konferenzort
Istanbul, Turkey
ISSN
PUB-ID

Zitieren

Schmidt T, Stoye J. Quadratic Time Algorithms for Finding Common Intervals in Two and More Sequences. In: Proc. of CPM 2004. LNCS. Vol 3109. 2004: 347-358.
Schmidt, T., & Stoye, J. (2004). Quadratic Time Algorithms for Finding Common Intervals in Two and More Sequences. Proc. of CPM 2004, LNCS, 3109, 347-358. doi:10.1007/978-3-540-27801-6_26
Schmidt, T., and Stoye, J. (2004). “Quadratic Time Algorithms for Finding Common Intervals in Two and More Sequences” in Proc. of CPM 2004 LNCS, vol. 3109, 347-358.
Schmidt, T., & Stoye, J., 2004. Quadratic Time Algorithms for Finding Common Intervals in Two and More Sequences. In Proc. of CPM 2004. LNCS. no.3109 pp. 347-358.
T. Schmidt and J. Stoye, “Quadratic Time Algorithms for Finding Common Intervals in Two and More Sequences”, Proc. of CPM 2004, LNCS, vol. 3109, 2004, pp.347-358.
Schmidt, T., Stoye, J.: Quadratic Time Algorithms for Finding Common Intervals in Two and More Sequences. Proc. of CPM 2004. LNCS. 3109, p. 347-358. (2004).
Schmidt, Thomas, and Stoye, Jens. “Quadratic Time Algorithms for Finding Common Intervals in Two and More Sequences”. Proc. of CPM 2004. 2004.Vol. 3109. LNCS. 347-358.