Sequence analysis The Global Trace Graph, a Novel Paradigm for Searching Protein Sequence D.pdfVIP

Bioinformatics Advance Access published September 6, 2007 Sequence analysis The Global Trace Graph, a Novel Paradigm for Searching Protein Sequence Databases Andreas Heger1,3, Swapan Mallick1,4, Christopher Wilton1,5 and Liisa Holm,*1,2 1Institute of Biotechnology and 2Department of Biological and Environmental Sciences, Division of Genetics, P.O.Box 56 (Viikinkaari 5), FI-00014 Univer- sity of Helsinki, Finland. 3 Current address: MRC Functional Genetics Unit, Department of Physiology, Anatomy Genetics, University of Oxford, South Parks Road, OX1 3QX Oxford, U.K. 4 Current address: Department of Gernetics, Harvard Medical School, Boston, MA. 5 Current address: Babraham Insti- tute, Cambridge, U.K. Associate Editor: Prof. Burkhard Rost ABSTRACT proteins (Heger et al. 2005, Kaplan et al. 2005, Heger Holm Motivation: Propagating functional annotations to sequence-similar, 2000 and references therein) have the advantage of completeness, presumably homologous proteins lies at the heart of the bioinformat- but the determination of the boundary between homologous and ics industry. Correct propagation is crucially dependent on the accu- unrelated sequences is unreliable or simply left to the user. To maximize information transfer, there is a need for methods which rate identification of subtle sequence motifs that are conserved in are able to traverse large evolutionary distances while discriminat- evolution. The evolutionary signal can be difficult to detect because ing against unrelated sequences. For example, a series