<XML><RECORDS><RECORD><REFERENCE_TYPE>7</REFERENCE_TYPE><REFNUM>7014</REFNUM><AUTHORS><AUTHOR>Gilbert,D.</AUTHOR><AUTHOR>Westhead,D.</AUTHOR><AUTHOR>Viksna,J.</AUTHOR></AUTHORS><YEAR>2003</YEAR><TITLE>Techniques for comparison, pattern matching and pattern discovery: From sequences to protein topology</TITLE><PLACE_PUBLISHED> </PLACE_PUBLISHED><PUBLISHER>IOS Press</PUBLISHER><PAGES>128-147</PAGES><ISBN>1-58603-294-1</ISBN><LABEL>Gilbert:2003:7014</LABEL><KEYWORDS><KEYWORD>Bioinformatics</KEYWORD></KEYWORDS<ABSTRACT>In this chapter we review techniques for sequence based pattern discovery and comparison, and show how these can be extended to RNA structures and abstract representations of protein structure at the fold level. We first define deterministic patterns over sequences and distinguish pattern matching from string comparison, reviewing the use of dynamic programming to compute edit distance, and longest common sub-sequence. We then describe approaches to pattern discovery in sequences and describe methods for evaluating the goodness of patterns. Next we show how string pattern languages can be extended to be applied to more complex data structures which can sequence and structural information, and give some algorithms for pattern discovery over certain classes of biosequences with structural content, with specific application to RNA. Finally we describe our work on pattern discovery and structure comparison for topological descriptions of protein structures, and show how these approaches can form the basis for practical and useful computational systems. </ABSTRACT></RECORD></RECORDS></XML>