Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Euclidean distance geometry : an introduction
Liberti L., Lavor C., Springer International Publishing, New York, NY, 2017. 133 pp. Type: Book (978-3-319607-91-7)
Date Reviewed: May 14 2019

If someone has a set of objects whose positions are known, calculating the distances between them is not a problem. However, the inverse problem is difficult, that is, given a set of distances between objects, determine their positions. Unfortunately, several solutions equivalently satisfy the requirements. Distinguishing among them is impossible without further information, for example, additional constraints may limit the number of solutions. Solving the problem is even more difficult if the given information is only partial. This is the core of the distance geometry problem.

The authors previously wrote a short monograph on the application of distance geometry in determining molecular structure [1]. This book is different: first, it is designed to be a textbook; second, the distance geometry problem is generalized as a mathematical problem and not specifically tied to a particular application area. As a textbook, it includes the usual expected features: downloadable software (Mathematica scripts), exercises at the end of each chapter, and a solution manual for the exercises.

The book is quite short--less than 140 pages, including the contents at the front and an index at the end. There are nine chapters and an appendix of mathematical facts and terminology. The book starts by assuming that the reader knows very little about distance geometry. The first two chapters are motivational, using examples to formally introduce readers to the distance geometry problem. The examples are very different--clock synchronization, sensor localization, structural biology, and big data analysis. The book presents the distance geometry problem using graph theory as the principal mathematical tool.

Chapters 3 and 4 further develop the graph-theoretical formulation by developing the properties of cliques and the reduction of large distance geometry problems into smaller subsets of points in cliques of reduced size. The fifth chapter returns to the molecular structure problem expressed in graph theory. The effects of molecular symmetry on the analysis are discussed, because molecular symmetries provide internal constraints on the solution space. Chapter 6, on vertex order, discusses the identification of vertices given merely a graph and a set of edge weights. The problem is tractable if there is a clique of known vertices upon which to build. This chapter would be pertinent to the example of locating a set of sensors where not all of the sensor positions are known.

Chapter 7, “Flexibility and Rigidity,” introduces the time dependency of structures. The terms themselves describe whether structures change (flexible) or do not change (rigid) with time. Rigidity means that a vertex in a rigid framework can move only if every other vertex connected to it moves, preserving the distances among them. The eighth chapter, “Approximate Realizations,” extends the analytical techniques to larger structures so that they can be reduced to smaller structures more amenable to analysis using the Gram matrix and principal component analysis. The last chapter is without exercises since it is an essay on the directions that the authors believe distance geometry will be going, including unsolved problems in both application areas and fundamental theory. The mathematical appendix at the end is only 20 pages, but it covers abstract algebra, linear algebra, graph theory, and complexity theory.

Since this is a textbook, the potential market is an important factor. The authors’ intended audience is undergraduate students. The book is intensely mathematical. It would probably be more suitable for graduate students in mathematics than undergraduates. Biochemistry and molecular biology students applying distance geometry would likely find the almost exclusively mathematical terminology a barrier to using the book. The authors refer to an out-of-print book by Gordon Crippen and Timothy Havel on the distance geometry problem [2] as an early book on the subject, although not a textbook. This book is still available in electronic form, since Crippen has released a PDF version online (https://www.researchgate.net/publication/268018683_Distance_Geometry_and_Molecular_Conformation). Readers in the physical or biological sciences should read it along with this textbook.

Reviewer:  Anthony J. Duben Review #: CR146570 (1908-0297)
1) Duben, A. J. Review of An introduction to distance geometry applied to molecular geometry, by C. Lavor et al. Computing Reviews (June 7, 2018), CR Rev. No. 146073 (1808-0413).
2) Crippen, G.; Havel, T. Distance geometry and molecular conformation. Wiley, New York, NY, 1988.
Bookmark and Share
  Reviewer Selected
Featured Reviewer
 
 
Geometrical Problems And Computations (F.2.2 ... )
 
 
Biology And Genetics (J.3 ... )
 
 
Constrained Optimization (G.1.6 ... )
 
 
Graph Algorithms (G.2.2 ... )
 
 
Applications (G.1.10 )
 
 
Mathematical Software (G.4 )
 
Would you recommend this review?
yes
no
Other reviews under "Geometrical Problems And Computations": Date
Some performance tests of convex hull algorithms
Allison D., Noga M. BIT 24(1): 2-13, 1984. Type: Article
Feb 1 1985
A fast voronoi-diagram algorithm with quaternary tree bucketing
Ohya T., Iri M., Murota K. Information Processing Letters 18(4): 227-231, 1984. Type: Article
Jan 1 1985
Convex partitions of polyhedra: a lower bound and worst-case optimal algorithm
Chazelle B. (ed) SIAM Journal on Computing 13(3): 488-507, 1984. Type: Article
Mar 1 1985
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy