Algorithms for phylogenetic footprinting

ABSTRACT

Phylogenetic footprinting is a technique that identifies regulatory elements by finding unusually well conserved regions in a set of orthologous non-coding DNA sequences from multiple species. In an earlier paper, we presented an exact algorithm that identifies the most conserved region of a set of sequences. Here, we present a number of algorithmic improvements that produce a 1000 fold speedup over the original algorithm. We also show how prior knowledge can be used to identify weaker motifs, and how to handle data sets in which only an unknown subset of the sequences contain the regulatory element. Each technique is implemented and successfully identifies a large number of known binding sites, as well as several highly conserved but uncharacterized regions.

REFERENCES

• 1: T. Akutsu. Hardness results on gapless local multiple sequence alignment. Technical Report 98-MPS-24-2, Information Processing Society of Japan, 1998.
• 2: R. D. Andersen, S. J. Taplitz, S. Wong, G. Bristol, B. Larkin, and H. R. Herschman. Metal-dependent binding of a factor in vivo to the metal-responsive elements of the metallothionein 1 gene promoter. Mol. Cell. Biol., 7:3574-3581, 1987.
• 3: G. Arguello-Astorga and L. Herrera-Estrella. Evolution of light-regulated plant promoters. Annu. Rev. Plant Physiol. Plant Mol. Biol., 49:525-555, 1998.
• 4: H. Ariga, Y. Imamura, and S. M. M. Iguchi-Ariga. DNA replication origin and transcriptional enhancer in c-myc gene share the c-myc protein binding sequences. EMBO J., 8:4273-4279, 1989.
• 5: Timothy L. Bailey , Charles Elkan, Unsupervised Learning of Multiple Motifs in Biopolymers Using Expectation Maximization, Machine Learning, v.21 n.1-2, p.51-80, Oct./Nov. 1995 [doi>10.1007/BF00993379]
• 6: M. Blanchette. An exact algorithm to identify motifs in orthologous sequences from multiple species. Technical Report, Qualification project, University of Washington, 2000.
• 7: Mathieu Blanchette , Benno Schwikowski , Martin Tompa, An Exact Algorithm to Identify Motifs in Orthologous Sequences from Multiple Species, Proceedings of the Eighth International Conference on Intelligent Systems for Molecular Biology, p.37-45, August 19-23, 2000
• 8: D. S. W. Boam, A. R. Clark, and K. Docherty. Positive and negative regulation of the human insulin gene by multiple trans-acting factors. J. Biol. Chem., 265:8285-8296, 1990.
• 9: L. Duret and P. Bucher. Searching for regulatory elements in human noncoding sequences. Curr. Op. in Struct. Biol., 7:399-405, 1997.
• 10: L. Duret, F. Dorkeld, and C. Gauthier. Strong conservation of non-coding sequences during vertebrates evolution: potential involvement in post-transcriptional regulation of gene expression. Nucleic Acids Research, 21, 10:2315-2322, 1993.
• 11: G. N. Filippova, S. Fagerlie, E. M. Klenova, C. Meyers, Y. Dehner, G. Goodwin, P. E. Neiman, S. J. Collins, and V. V. Lobanenkov. An exceptionally conserved transcriptional repressor, ctcf, employs different combinations of zinc fingers to bind diverged promoter sequences of avian and mammalian c-myc oncogenes. Mol. Cell. Biol., 16:2802-2813, 1996.
• 12: R. M. Frederickson, M. R. Micheau, A. Iwamoto, and N. G. Miyamoto. 5 flanking and first intron sequences of the human beta-actin gene required for efficient promoter activity. Nucleic Acids Res., 17:253-270, 1989.
• 13: D. Gumucio, D. Shelton, W. Bailey, J. Slightom, and M. Goodman. Phylogenetic footprinting reveals unexpected complexity in trans factor binding upstream from the c-globin gene. Proc. Natl. Acad. Sci. USA, 90:6018-6022, 1993.
• 14: Dan Gusfield, Algorithms on strings, trees, and sequences: computer science and computational biology, Cambridge University Press, New York, NY, 1997
• 15: G. Z. Hertz and G. D. Stormo. Identifying DNA and protein patterns with statistically significant alignments of multiple sequences. Bioinformatics, 15(7/8):563-577, July/August 1999.
• 16: S. W. Hiebert, M. Lipp, and N. J. R. Ela-dependent trans-activation of the human myc promoter is mediated by the e2f factor. Proc. Natl. Acad. Sci. USA, 86:3594-3598, 1989.
• 17: D. G. Higgins, J. D. Thompson, and T. J. Gibson. Using CLUSTAL for multiple sequence alignments. In R. F. Doolittle, editor, Computer Methods for Macromolecular Sequence Analysis, volume 266 of Methods in Enzymology, pages 383-401. Academic Press, New York, 1996.
• 18: J. Hughes, P. Estep, S. Tavazoie, and G. Church. Computational identification of cis-regulatory elements associated with groups of functionally related genes in Saccharomyces cerevisiae. J. Mol. Biol., 296(5):1205-14, 2000.
• 19: T. Kawamoto, K. Makino, H. Niwa, H. Sugiyama, S. Kimura, M. Amemura, A. Nakata, and T. Kakunaga. Identification of the human beta-actin enhancer and its binding factor. Mol. Cell. Biol., 8:267-272, 1988.
• 20: E. Kislauskis, X. Zhu, and R. Singer. Sequences responsible for intracellular localization of betaactin messenger RNA also affect cell phenotype. J. Cell. Biol., 127:441-451, 1994.
• 21: J. Leung, E. McKenzie, A. Uglialoro, P. Florez-Villanueva, B. Sorkin, E. Yunis, D. Hartl, and A. Goldfeld. Identification of phylogenetic footprints in primate tumor necrosis factor-a promoters. Proc. Natl. Acad. Sci. USA, 97, 12:6614-6618, 2000.
• 22: J. F. Marten, V. Savolainen, and P. Simon. The atpB and rbcL promoters in plastid DNAs of a wide dicot range. Journal of Molecular Evolution, 38(6):577-582, June 1994.
• 23: A. L. Means and P. G. Farnham. Transcription initiation from the dihydrofolate reductase promoter is positioned by hip1 binding at the initiation site. Mol. Cell. Biol., 10:653-661, 1990.
• 24: S. Natesan and M. Gilman. Yyl facilitates the association of serum response factor with the c-fos serum response element. Mol. Cell. Biol., 15:5975-5982, 1995.
• 25: Pavel A. Pevzner , Sing-Hoi Sze, Combinatorial Approaches to Finding Subtle Signals in DNA Sequences, Proceedings of the Eighth International Conference on Intelligent Systems for Molecular Biology, p.269-278, August 19-23, 2000
• 26: D. Sankoff and P. Rousseau. Locating the vertices of a Steiner tree in arbitrary metric space. Mathematical Programming, 9:240-246, 1975.
• 27: Saurabh Sinha , Martin Tompa, A Statistical Method for Finding Transcription Factor Binding Sites, Proceedings of the Eighth International Conference on Intelligent Systems for Molecular Biology, p.344-354, August 19-23, 2000
• 28: D. Tagle, B. Koop, M. Goodman, J. Slightom, D. Hess, and R. Jones. Embryonic and globin genes of a prosimian primate (Galago crassicaudatus) nucleotide and amino acid sequences, developmental regulation and phylogenetic footprints. J. Mol. Biol., 203:439-455, 1988.
• 29: S. Tavazoie, J. D. Hughes, M. J. Campbell, R. J. Cho, and G. M. Church. Systematic determination of genetic network architecture. Nature Genetics, 22:281-285, July 1999.
• 30: S. Vuillaumier, I. Dixmeras, H. Messai., C. Lapoumeroulie, D. Lallemand, J. Gekas, F. Chebab, C. Perret, J. Elion, and E. Denamur. Cross-species characterization of the promoter region of the cystic fibrosis transmembrane conductance regulator gene reveals multiple levels of regulation. Biochem J., 327:652-662, 1997.
• 31: L. Wang and T. Jiang. On the complexity of multiple sequence alignment. Journal of Computational Biology, 1:337-348, 1994.
• 32: E. Wingender, P. Dietze, H. Karas, and R. Knfippel. TRANSFAC: a database on transcription factors and their DNA binding sites. Nucleic Acids Research, 24(1):238-241, 1996. http://transfac, gbf-braunschweig, de/TRANSFAC/.

INDEX TERMS

Primary Classification:
  J. Computer Applications
  J.3 LIFE AND MEDICAL SCIENCES
      Subjects: Biology and genetics

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Dynamic programming

General Terms:
Algorithms, Design, Human Factors, Measurement, Performance, Theory

Keywords:
algorithm, motif finding, phylogenetic footprinting, phylogeny, regulatory elements