An Introduction to Bioinformatics algorithms www.bioalgorithms.info One More Partial Digest Example X024710 24710 0247 25 3 863 10 Representation of DX=(2, 2, 3, 3, 4, 5, 6,7,8, 10]as a two dimensional table, with elements of X={0,2,4,7,10} along both the top and left side. The elements at(,D in the table for 1si<jsn
An Introduction to Bioinformatics Algorithms www.bioalgorithms.info One More Partial Digest Example X 0 2 4 7 10 0 2 4 7 10 2 2 5 8 4 3 6 7 3 10 Representation of DX = {2, 2, 3, 3, 4, 5, 6, 7, 8, 10} as a two dimensional table, with elements of X = {0, 2, 4, 7, 10} along both the top and left side. The elements at (i, j) in the table is xj – xi for 1 ≤ i < j ≤ n
An Introduction to Bioinformatics algorithms www.bioalgorithms.info Partial Digest Problem: Formulation Goal: Given_all pairwise distances between points on a line, reconstruct the positions of those points Input: The multiset of pairwise distances L, containing n(n-1)/2 integers Output: A set X, of n integers, such that DX= L
An Introduction to Bioinformatics Algorithms www.bioalgorithms.info Partial Digest Problem: Formulation Goal: Given all pairwise distances between points on a line, reconstruct the positions of those points • Input: The multiset of pairwise distances L, containing n(n-1)/2 integers • Output: A set X, of n integers, such that DX = L
An Introduction to Bioinformatics algorithms www.bioalgorithms.info Partial Digest: Multiple Solutions It is not always possible to uniquely reconstruct a set X based only on DX. For example, the set X={0,2,5} and (X+10)={10,12,15} both produce DX(2, 3, 5] as their partial digest set The sets{0,1,2,5,7,9,12}and{0,1,5,7,8,10,12} present a less trivial example of non-uniqueness. They both digest into ,1,2,2,2,3,3,4,4,5,5,5,6,7,7,7,8,9,10,11,12}
An Introduction to Bioinformatics Algorithms www.bioalgorithms.info Partial Digest: Multiple Solutions • It is not always possible to uniquely reconstruct a set X based only on DX. • For example, the set X = {0, 2, 5} and (X + 10) = {10, 12, 15} both produce DX={2, 3, 5} as their partial digest set. • The sets {0,1,2,5,7,9,12} and {0,1,5,7,8,10,12} present a less trivial example of non-uniqueness. They both digest into: {1, 1, 2, 2, 2, 3, 3, 4, 4, 5, 5, 5, 6, 7, 7, 7, 8, 9, 10, 11, 12}
An Introduction to Bioinformatics algorithms www.bioalgorithms.info Homometric Sets 01257912 015781012 2579120 5781012 46811 46|7911 2 35|710 2|357 24|7 13|5 2 24 10 2 12 12
An Introduction to Bioinformatics Algorithms www.bioalgorithms.info Homometric Sets 0 1 2 5 7 9 12 0 1 2 5 7 9 12 1 1 4 6 8 11 2 3 5 7 10 5 2 4 7 7 2 5 9 3 12 0 1 5 7 8 10 12 0 1 5 7 8 10 12 1 4 6 7 9 11 5 2 3 5 7 7 1 3 5 8 2 4 10 2 12