Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/58144
Type: Artigo de periódico
Title: Thermodynamical approach to the longest common subsequence problem
Author: Amsalu, S
Matzinger, H
Vachkovskaia, M
Abstract: We introduce an interacting particle model in a random media and show that this particle process is equivalent to the Longest Common Subsequence (LCS) problem of two binary sequences. We derive a differential equation which links the mean LCS-curve to the average speed of the particles given their density and prove that the average speed of the particles and density converges uniformly on every scale which is somewhat larger than root n.
Subject: longest common subsequence
interacting particle systems
optimal sequence alignment
Country: EUA
Editor: Springer
Rights: fechado
Identifier DOI: 10.1007/s10955-008-9533-z
Date Issue: 2008
Appears in Collections:Unicamp - Artigos e Outros Documentos

Files in This Item:
File Description SizeFormat 
WOS000256085700006.pdf404.89 kBAdobe PDFView/Open


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