Krusche, Peter and Tiskin, Alexander (2009) String comparison by transposition networks. In: London Algorithmics 2008: Theory and Practice. London: College Publications, pp. 184-204. ISBN 9781904987970

PDF 0903.pdf Restricted to Repository staff only - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader Download (223Kb)

Abstract

Computing string or sequence alignments is a classical method of comparing strings and has applications in many areas of computing, such as signal processing and bioinformatics. Semi-local string alignment is a recent generalisation of this method, in which the alignment of a given string and all substrings of another string are computed simultaneously at no additional asymptotic cost. In this paper, we show that there is a close connection between semi-local string alignment and a certain class of traditional comparison networks known as transposition networks. The transposition network approach can be used to represent different string comparison algorithms in a unified form, and in some cases provides generalisations or improvements on existing algorithms. This approach allows us to obtain new algorithms for sparse semi-local string comparison and for comparison of highly similar and highly dissimilar strings, as well as of run-length compressed strings. We conclude that the transposition network method is a very general and flexible way of understanding and improving different string comparison algorithms, as well as their efficient implementation.

Item Type:	Book Item
Subjects:	Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software
Divisions:	Faculty of Science > Computer Science
Publisher:	College Publications
Place of Publication:	London
ISBN:	9781904987970
Book Title:	London Algorithmics 2008: Theory and Practice
Date:	1 June 2009
Volume:	11
Page Range:	pp. 184-204
Status:	Not Peer Reviewed
Publication Status:	Published
Access rights to Published version:	Restricted or Subscription Access
Description:	A volume dedicated to Maxime Crochemore on his 60th birthday.
Open Access Version:	ArXiv
URI:	http://wrap.warwick.ac.uk/id/eprint/47533

Request changes to a record

Actions (login required)

View Item