Structure from unassigned distance lists: theorems, algorithms and key challenges
After a quick introduction to the assigned and unassigned cases of distance geometry and their applications, the concept of generic distance lists is developed. For generic distance lists, structure can be found from unassigned lists, provided there are enough distances in the list, that the distances are randomly selected, and the distances are precise. Lower bounds on the number of distances needed to find structure are presented, and precise algorithms are outlined including exact combinatorial approaches and continuous optimization variants. Discussion of cases where the cardinality of a distance list is insufficient for structure determination follows, particularly discretizable cases. Approaches to cases where the distances are not precise are more challenging, however heuristic methods are helpful and will be surveyed.The talk will close with some outstanding mathematical and algorithmic challenges, including:
* Can these methods be used for non-generic distance lists, if so how?
* When enough precise distances are provided, structure can be found using polynomial growth algorithms. However an outstanding question is whether for solvable cases, there is there an easy to hard transition as the number of edges decreases or they are no randomly placed?
* What happens when the uncertainty in the distances increases? Can we prove that some cases are solvable in polynomial time? How many distances are needed? Is there an easy-hard transition.
* How can we improve heuristic or exact algorithms
PS. This work was done in collaboration with many others as indicated in our recent reviews and publications.