TY - GEN
T1 - A characterization of the number of subsequences obtained via the deletion channel
AU - Liron, Y.
AU - Langberg, M.
PY - 2012
Y1 - 2012
N2 - Motivated by the study of deletion channels, this work presents improved bounds on the number of subsequences obtained from a binary sting X of length n under t deletions. It is known that the number of subsequences in this setting strongly depends on the number of runs in the string X; where a run is a maximal sequence of the same character. Our improved bounds are obtained by a structural analysis of the family of r-run strings X, an analysis in which we identify the extremal strings with respect to the number of subsequences. Specifically, for every r, we present r-run strings with the minimum (respectively maximum) number of subsequences under any t deletions; and perform an exact analysis of the number of subsequences of these extremal strings.
AB - Motivated by the study of deletion channels, this work presents improved bounds on the number of subsequences obtained from a binary sting X of length n under t deletions. It is known that the number of subsequences in this setting strongly depends on the number of runs in the string X; where a run is a maximal sequence of the same character. Our improved bounds are obtained by a structural analysis of the family of r-run strings X, an analysis in which we identify the extremal strings with respect to the number of subsequences. Specifically, for every r, we present r-run strings with the minimum (respectively maximum) number of subsequences under any t deletions; and perform an exact analysis of the number of subsequences of these extremal strings.
UR - https://www.scopus.com/pages/publications/84867533197
U2 - 10.1109/ISIT.2012.6284240
DO - 10.1109/ISIT.2012.6284240
M3 - ???researchoutput.researchoutputtypes.contributiontobookanthology.conference???
AN - SCOPUS:84867533197
SN - 9781467325790
T3 - IEEE International Symposium on Information Theory - Proceedings
SP - 503
EP - 507
BT - 2012 IEEE International Symposium on Information Theory Proceedings, ISIT 2012
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 2012 IEEE International Symposium on Information Theory, ISIT 2012
Y2 - 1 July 2012 through 6 July 2012
ER -