Biblioteca Digital do Instituto Politécnico de Bragança   Instituto Politécnico de Bragança

Biblioteca Digital do IPB >
Escola Superior Agrária >
Ciências Sociais e Exactas >
CSE - Capítulos de Livros >

Please use this identifier to cite or link to this item: http://hdl.handle.net/10198/4385

Título: SimSearch: A new variant of dynamic programming based on distance series for optimal and near-optimal similarity discovery in biological sequences
Autor: Deusdado, Sérgio
Carvalho, Paulo
Palavras-chave: Similarity discovery
Dynamic programming
Distance series
Issue Date: 2008
Editora: Springer-Verlag
Citação: Deusdado, Sérgio; Carvalho, Paulo (2008) - SimSearch: A new variant of dynamic programming based on distance series for optimal and near-optimal similarity discovery in biological sequences. In Corchado, Juan M. 2nd International Workshop on Practical Applications of Computational Biology and Bioinformatics. Berlin: Springer-Verlag. p. 206-216. ISBN 978-3-540-85860-7. (Advances in Soft Computing; 49)
Resumo: In this paper, we propose SimSearch, an algorithm implementing a new variant of dynamic programming based on distance series for optimal and near-optimal similarity discovery in biological sequences. The initial phase of SimSearch is devoted to fulfil the binary similarity matrices by signalling the distances between occurrences of the same symbol. The scoring scheme is further applied, when analysed the maximal extension of the pattern. Employing bit parallelism to analyse the global similarity matrix’s upper triangle, the new methodology searches the sequence(s) for all the exact and approximate patterns in regular or reverse order. The algorithm accepts parameterization to work with greater seeds for near-optimal results. Performance tests show significant efficiency improvement over traditional optimal methods based on dynamic programming. Comparing the new algorithm’s efficiency against heuristic based methods, equalizing the required sensitivity, the proposed algorithm remains acceptable.
URI: http://hdl.handle.net/10198/4385
ISBN: 978-3-540-85860-7
Versão do Editor: http://www.springerlink.com/content/t3701n3011675773/
Appears in Collections:CSE - Capítulos de Livros

Files in This Item:

File Description SizeFormat
2008-SimSearch_deusdado_carvalho_Salamanca.pdf90,21 kBAdobe PDFView/Open

Please give feedback about this item
Statistics
FacebookTwitterDeliciousLinkedInDiggGoogle BookmarksMySpace
Formato BibTex MendeleyEndnote Logotipo do DeGóis 

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

 


© Instituto Politécnico de Bragança - Biblioteca Digital - Feedback - Statistics
Promotores do RCAAP   Financiadores do RCAAP

Fundação para a Ciência e a Tecnologia Universidade do Minho   Governo Português Ministério da Educação e Ciência PO Sociedade do Conhecimento (POSC) Portal oficial da União Europeia