From Longest Common Subsequences to Scenery Reconstruction
- Series
- Research Horizons Seminar
- Time
- Tuesday, March 9, 2010 - 12:00 for 1 hour (actually 50 minutes)
- Location
- Skiles 255
- Speaker
- Heinrich Matzinger – Professor, School of Mathematics
Please Note: Hosted by: Huy Huynh and Yao Li
The Scenery Reconstruction Problem consists in trying to reconstruct
a coloring of the integers given only the observations made by
a random walk. For this we consider a random walk S and
a coloring of the integers X. At time $t$ we observe
the color $X(S(t))$. The coloring is i.i.d. and we show that
given only the sequence of colors
$$X(S(0)),X(S(1)),X(S(2)),...$$
it is possible to reconstruct $X$ up to translation
and reflection. The solution depends on the property of the
random walk and the distribution of the coloring.
Longest Common Subsequences (LCS) are widely used in genetics.
If we consider two sequences X and Y, then a common subsequence
of X and Y is a string which is a subsequence of X and of Y at the same
time. A Longest Common Subsequence of X and Y is a common
subsequence of X and Y of maximum length. The problem of the asymptotic
order of the flucutation for the LCS of independent random
strings has been open for decades. We have now been able to
make progress on this problem for several important cases.
We will also show the connection to the Scenery Reconstruction
Problem.