ÿþ<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:st1="urn:schemas-microsoft-com:office:smarttags" xmlns="http://www.w3.org/TR/REC-html40"> <head> <meta http-equiv=Content-Type content="text/html; charset=unicode"> <meta name=ProgId content=Word.Document> <meta name=Generator content="Microsoft Word 10"> <meta name=Originator content="Microsoft Word 10"> <link rel=File-List href="April30-2003_files/filelist.xml"> <link rel=Edit-Time-Data href="April30-2003_files/editdata.mso"> <!--[if !mso]> <style> v\:* {behavior:url(#default#VML);} o\:* {behavior:url(#default#VML);} w\:* {behavior:url(#default#VML);} .shape {behavior:url(#default#VML);} </style> <![endif]--> <title>Seminar: July 09, 2002</title> <o:SmartTagType namespaceuri="urn:schemas-microsoft-com:office:smarttags" name="PlaceType"/> <o:SmartTagType namespaceuri="urn:schemas-microsoft-com:office:smarttags" name="PlaceName"/> <o:SmartTagType namespaceuri="urn:schemas-microsoft-com:office:smarttags" name="place"/> <!--[if gte mso 9]><xml> <o:DocumentProperties> <o:Author>Dide Ergüven</o:Author> <o:LastAuthor>Dide Ergüven</o:LastAuthor> <o:Revision>3</o:Revision> <o:TotalTime>5</o:TotalTime> <o:Created>2003-04-29T06:11:00Z</o:Created> <o:LastSaved>2003-04-29T10:07:00Z</o:LastSaved> <o:Pages>1</o:Pages> <o:Words>277</o:Words> <o:Characters>1585</o:Characters> <o:Company>Bilkent Üniversitesi</o:Company> <o:Lines>13</o:Lines> <o:Paragraphs>3</o:Paragraphs> <o:CharactersWithSpaces>1859</o:CharactersWithSpaces> <o:Version>10.2625</o:Version> </o:DocumentProperties> </xml><![endif]--><!--[if gte mso 9]><xml> <w:WordDocument> <w:SpellingState>Clean</w:SpellingState> <w:GrammarState>Clean</w:GrammarState> <w:BrowserLevel>MicrosoftInternetExplorer4</w:BrowserLevel> </w:WordDocument> </xml><![endif]--><!--[if !mso]><object classid="clsid:38481807-CA0E-42D2-BF39-B33AF135CC4D" id=ieooui></object> <style> st1\:*{behavior:url(#ieooui) } </style> <![endif]--> <style> <!--a:link {font-weight: Regular;} a:visited {font-weight: Regular;} a:active {font-weight: Regular;} A:hover { color: #A0A0A0 } h2 {FONT-FACE: Bold;} /* Font Definitions */ @font-face {font-family:Verdana; panose-1:2 11 6 4 3 5 4 4 2 4; mso-font-charset:162; mso-generic-font-family:swiss; mso-font-pitch:variable; mso-font-signature:536871559 0 0 0 415 0;} @font-face {font-family:"Century Gothic"; panose-1:2 11 5 2 2 2 2 2 2 4; mso-font-charset:162; mso-generic-font-family:swiss; mso-font-pitch:variable; mso-font-signature:647 0 0 0 159 0;} @font-face {font-family:"Trebuchet MS"; panose-1:2 11 6 3 2 2 2 2 2 4; mso-font-charset:162; mso-generic-font-family:swiss; mso-font-pitch:variable; mso-font-signature:647 0 0 0 159 0;} /* Style Definitions */ p.MsoNormal, li.MsoNormal, div.MsoNormal {mso-style-parent:""; margin:0cm; margin-bottom:.0001pt; mso-pagination:widow-orphan; font-size:12.0pt; font-family:"Times New Roman"; mso-fareast-font-family:"Times New Roman"; color:black;} h2 {mso-margin-top-alt:auto; margin-right:0cm; mso-margin-bottom-alt:auto; margin-left:0cm; mso-pagination:widow-orphan; mso-outline-level:2; font-size:12.0pt; font-family:Verdana; color:black; font-weight:bold;} h3 {mso-margin-top-alt:auto; margin-right:0cm; mso-margin-bottom-alt:auto; margin-left:0cm; mso-pagination:widow-orphan; mso-outline-level:3; font-size:13.5pt; font-family:"Times New Roman"; color:black; font-weight:bold;} a:link, span.MsoHyperlink {color:blue; mso-text-animation:none; text-decoration:none; text-underline:none; text-decoration:none; text-line-through:none;} a:visited, span.MsoHyperlinkFollowed {color:blue; mso-text-animation:none; text-decoration:none; text-underline:none; text-decoration:none; text-line-through:none;} p {mso-margin-top-alt:auto; margin-right:0cm; mso-margin-bottom-alt:auto; margin-left:0cm; mso-pagination:widow-orphan; font-size:12.0pt; font-family:"Times New Roman"; mso-fareast-font-family:"Times New Roman"; color:black;} span.SpellE {mso-style-name:""; mso-spl-e:yes;} span.GramE {mso-style-name:""; mso-gram-e:yes;} @page Section1 {size:612.0pt 792.0pt; margin:70.85pt 70.85pt 70.85pt 70.85pt; mso-header-margin:35.4pt; mso-footer-margin:35.4pt; mso-paper-source:0;} div.Section1 {page:Section1;} --> </style> <!--[if gte mso 10]> <style> /* Style Definitions */ table.MsoNormalTable {mso-style-name:"Table Normal"; mso-tstyle-rowband-size:0; mso-tstyle-colband-size:0; mso-style-noshow:yes; mso-style-parent:""; mso-padding-alt:0cm 5.4pt 0cm 5.4pt; mso-para-margin:0cm; mso-para-margin-bottom:.0001pt; mso-pagination:widow-orphan; font-size:10.0pt; font-family:"Times New Roman";} </style> <![endif]--><!--[if gte mso 9]><xml> <o:shapedefaults v:ext="edit" spidmax="3074"/> </xml><![endif]--><!--[if gte mso 9]><xml> <o:shapelayout v:ext="edit"> <o:idmap v:ext="edit" data="1"/> </o:shapelayout></xml><![endif]--> </head> <body bgcolor=white lang=EN-US link=blue vlink=blue style='tab-interval:36.0pt'> <div class=Section1> <p class=MsoNormal> <link rev=made href="mailto:guvenir@cs.bilkent.edu.tr"> <span style='font-family:Arial'><a href="http://www.bilkent.edu.tr" title="Bilkent Üniversitesi"><span style='font-size:13.5pt;color:navy'><!-- OWNER_INFO="Bilkent University, Department of Computer Engineering -->Bilkent University</span></a><br> <a href="http://www.cs.bilkent.edu.tr" title="Bilgisayar Mühendislii Bölümü"><span style='font-size:13.5pt;color:red'>Department of Computer Engineering</span></a> <o:p></o:p></span></p> <div class=MsoNormal align=center style='text-align:center'><span style='font-family:Arial'> <hr size=2 width="100%" noshade color=navy align=center> </span></div> <p class=MsoNormal align=center style='text-align:center'><b><span style='font-size:13.5pt;font-family:"Century Gothic";mso-bidi-font-family:Arial; color:#007744'>S E M I N A R</span></b><span style='font-family:"Century Gothic"; mso-bidi-font-family:Arial'> <o:p></o:p></span></p> <h2 align=center style='text-align:center'><span style='font-size:18.0pt; font-family:"Century Gothic";mso-bidi-font-family:Arial;color:navy;font-weight: normal'>Distance-Based Indexing and Similarity Search for Genomic Sequences </span><span style='mso-bidi-font-family:Arial'><o:p></o:p></span></h2> <p align=center style='text-align:center'><span style='font-family:"Century Gothic"; mso-bidi-font-family:Arial'>&nbsp;<o:p></o:p></span></p> <h3 align=center style='text-align:center'><span style='font-family:"Century Gothic"'>Prof. Dr. Z. <span class=SpellE>Meral</span> <span class=SpellE>Özsoyolu</span><o:p></o:p></span></h3> <p align=center style='margin-top:0cm;margin-right:0cm;margin-bottom:6.0pt; margin-left:0cm;text-align:center'><span style='font-size:13.5pt;font-family: "Century Gothic";mso-bidi-font-family:Arial;color:gray'>Department of Electrical Engineering and Computer Science <o:p></o:p></span></p> <p align=center style='margin-top:0cm;margin-right:0cm;margin-bottom:6.0pt; margin-left:0cm;text-align:center'><st1:place><st1:PlaceName><span style='font-size:13.5pt;font-family:"Century Gothic";mso-bidi-font-family: Arial;color:gray'>Case</span></st1:PlaceName><span style='font-size:13.5pt; font-family:"Century Gothic";mso-bidi-font-family:Arial;color:gray'> </span><st1:PlaceName><span style='font-size:13.5pt;font-family:"Century Gothic";mso-bidi-font-family: Arial;color:gray'>Western Reserve</span></st1:PlaceName><span style='font-size:13.5pt;font-family:"Century Gothic";mso-bidi-font-family: Arial;color:gray'> </span><st1:PlaceType><span style='font-size:13.5pt; font-family:"Century Gothic";mso-bidi-font-family:Arial;color:gray'>University</span></st1:PlaceType></st1:place><span style='font-size:13.5pt;font-family:"Century Gothic";mso-bidi-font-family:Arial; color:gray'> <o:p></o:p></span></p> <p align=center style='text-align:center'><b><span style='font-size:10.0pt; font-family:"Century Gothic";mso-bidi-font-family:Arial;color:gray'>&nbsp;</span></b><span style='font-family:"Century Gothic";mso-bidi-font-family:Arial'>&nbsp;<o:p></o:p></span></p> <p class=MsoNormal style='mso-margin-top-alt:auto;margin-bottom:12.0pt'><span style='font-family:"Trebuchet MS"'>Finding sequences similar to a given query sequence in a large collection of sequences is a fundamental problem in many database applications including, computational genomics, computational finance, image and text processing. The similarity between sequences is defined in terms of a distance function determined by the application domain. In this work, we consider sequence proximity search in computational genomics, where sequence similarity is usually an indication of an evolutionary relationship between DNA and protein sequences, and usually indicates functional similarity. The most popular distance measures are based on (a weighted) count of character edit or block edit operations to transform one string to another. The main goal is to develop efficient near neighbor search tools that work for both character edit and block edit distances. Our premise is that the Distance Based Indexing techniques, which are originally developed for metric distances can be modified for sequence distance measures provided that they are almost metrics. We first show <span class=GramE>that</span> sequence distance functions of interest (compression distance and weighted character edit distance) are almost metric. We then show how to modify distance based index structures vantage point trees to accommodate almost metric distances. We test our theoretical results on synthetic data sets and protein sequences. </span></p> <p><span style='font-family:Verdana;mso-bidi-font-family:Arial'><br> &nbsp;</span><span style='font-family:Arial'><o:p></o:p></span></p> <p><b><span style='font-family:Arial;color:red'>DATE:</span></b><b><span style='font-family:Arial'> April 30, 2003, Wednesday @ 16:40 <br> </span></b><b><span style='font-family:Arial;color:red'>PLACE:</span></b><b><span style='font-family:Arial'> EA-409</span></b><span style='font-family:Arial'><o:p></o:p></span></p> </div> </body> </html>