Dendral

From Wikipedia, the free encyclopedia

You have new messages (last change).

During mid 20th century, the question “can machines think?” became intriguing and very popular among the “scientific” community primarily to add humanistic characteristics to machine behavior. John McCarthy, who was one of the prime researchers of this field, termed this concept of machine intelligence as "artificial intelligence” or simply “AI” during the Dartmouth summer in 1956. Artificial intelligence is usually defined as the capacity of a machine to perform operations that are analogous to human cognitive capabilities [1]. A large amount of research was concentrated during 20th century to determine how to incorporate this concept of artificial intelligence into machines. One of the most influential AI projects undertaken in 1960s was the Dendral Project. It spans approximately half the history of artificial intelligence research [2]. The word “Dendral” is a pruned version of “Dendritic Algorithm”[3]. It was designed and developed at Stanford University in 1965 by collaboration between Edward Feigenbaum, Bruce Buchanan, Joshua Lederberg, and Carl Djerassi [4] . The primary aim of Dendral was to aid organic chemists with identification of unknown organic molecules by analyzing information from mass spectrometry graphs and the knowledge of chemistry [5]. Thus, it is not surprising why Dendral is considered to be the first expert system because it automated the decision-making process and problem-solving behavior used by organic chemists to identify complex unknown organic molecules [6].

Contents

[edit] Basis of Dendral

“Dendral” is not just a single program but rather a product of an interaction between two sub programs known as “Heuristic Dendral” and “Meta-Dendral” [7]. It is written in Lisp (programming language), which is considered to be the language of artificial intelligence [8].

[edit] Heuristic Dendral

Heuristic Dendral is a program that receives mass spectrometry and other experimental data as an input, and incorporates this input with the knowledge base of chemistry to produce a set of possible chemical structures that correlate with the data as an output [9]. In other words, the mass spectrometer would first analyze the unknown organic compound by determining its molecular weight through the addition of the mass of its atomic constituents, and then feed that information into the Heuristic Dendral. For example, if the unknown compound was water (H2O), the mass spectrometer would input mass = 18, since H=1.01 and O=16.00 into the Heuristic Dendral. The Heuristic Dendral would now use this input mass, and the specific knowledge of chemistry which primarily includes mass numbers and valence rules of atoms to determine the possible combinations of atomic constituents whose mass would add up to 18 [10]. Thus, in this case it is H, O, and H. However, everything is not as simple as water. As the weight increases and the molecules become more complex, the number of possible chemical compounds that might correspond to that specific weight increases drastically. Thus, a program that is able to reduce this number of candidate solutions through the process of hypothesis formation is essential.

[edit] Meta-Dendral

Meta-Dendral is a knowledge acquisition system that receives the set of possible chemical structures and corresponding mass spectrometry graphs as input, and uses this information to propose a set of “hypotheses” that might explain correlation between some of the proposed structures and the mass spectrometry graph [11]. These “hypotheses” would be fed back into Heuristic Dendral to “test their applicability” [12]. Thus, “Heuristic Dendral is a performance system and Meta-Dendral is a learning system [13].” The basis of this programs lies in two important features: 1) the plan-generate-test paradigm; and 2) knowledge engineering [14].

[edit] Plan-generate-test paradigm

The plan-generate-test paradigm is the basic organization of the problem-solving method, and is a common paradigm used by both Heuristic Dendral and Meta-Dendral systems [15]. The generator generates potential solutions for a particular problem, which are then expressed as chemical graphs in Dendral [16]. However, this is feasible only when the number of candidate solutions is minimal. When there are large numbers of possible solutions, Dendral has to find a way to put constraints that rules out large sets of candidate solutions [17]. This is the primary aim of Dendral planner, which is a “hypothesis-formation” program that employs “task-specific knowledge to find constraints for the generator” [18]. Last but not least, the tester analyzes each proposed candidate solution and discards those that fail to fulfill certain criteria [19]. This mechanism of plan-generate-test paradigm is what holds Dendral together [20].

[edit] Knowledge Engineering

The primary aim of knowledge engineering is to attain a productive interaction between the available knowledge base and problem solving techniques [21]. This is possible through development of a procedure in which large amounts of task-specific information is encoded into heuristic programs [22]. Thus, the first essential component of knowledge engineering is a large “knowledge base.” The knowledge base would include specific knowledge about the mass spectrometry technique, large amount of information that forms the basis of chemistry and graph theory, and any information that might be helpful in finding the solution of a particular chemical structure elucidation problem [23]. Through knowledge engineering Dendral is able to use this “knowledge base” to both determine the set of possible chemical structures that correspond to the input data, and form new “general rules” that helps it reduce the number of candidate solutions. Thus, at the end the user is now provided with a minimal number of possible solutions, which can now be tested by any non-expert user to find the right solution.

[edit] Heuristics

A major approach of artificial intelligence is “heuristics programming” [24]. It became prominent in the scientific community in the late 1940s through George Polya’s book, How to Solve It: A New Aspect of Mathematical Method [25]. “Heuristics” are derivatives of algorithmic methods that do not guarantee a solution, but reduce the number of possibilities by discarding candidate solutions that are “unlikely” or “irrelevant” [26]. The use of heuristics programming was a giant step forward in the field of artificial intelligence, as it allowed scientists to finally automate certain traits of human intelligence. As Herbert Simon in The Sciences of the Artificial said, “if you take a heuristic conclusion as certain, you may be fooled and disappointed; but if you neglect heuristic conclusions altogether you will make no progress at all.” The use of “heuristic programming” by Dendral allowed it to replicate in machines the process through which human experts induce the solution to problems via rules of thumb and specific information. As such, Dendral is typically recognized as the first expert system.

[edit] How was Dendral conceived?

Around mid 20th century, the field of science especially biology was facing a major instrumentation crisis. The need for development of “man-computer symbiosis” to aid scientists in finding a solution to any particular problem was increasing drastically [27]. For example, the structural analysis of myogoblin, hemoglobin, and other proteins relentlessly needed instrumentation development due to the intense complexity of the process.

In early 1960s, Joshua Lederberg started working with the computers and quickly became tremendously interested in developing interactive computers that might help him in his exobiology research [28]. Specifically, Lederberg was interested in designing computing systems that might help him study alien organic compounds [29]. However, Lederberg himself was not an “expert” in either chemistry or computer programming. Thus, he collaborated with Stanford chemistry Carl Djerassi to help him with the “chemistry” side, and Edward Feigenbaum with the programming side of automating the process of determining chemical structures from raw mass spectrometry data [30]. Edward Feigenbaum, who was an expert in programming languages and heuristics helped Lederberg design a system that replicated the way Djerassi solved structure elucidation problems [31]. They devised a system called Dendritic Algorithm or Dendral that was able to generate possible chemical structures corresponding to the mass spectrometry data as an output [32].

However, Dendral was still very “incompetent” in accurately assessing spectra of ketones, alcohols, and isomers of same chemical compounds [33]. Thus, as seen in figure 1, Carl Djerassi “taught” general rules to Dendral that could help eliminate most of the “chemically implausible” structures, and produce a set of structures that could now be analyzed by a “non-expert” user to determine the right structure [34]. Furthermore, after all the general rules were entered into the knowledge base of Dendral, figure 2 shows how Dendral operates without an expert [35].

Image:November1.jpg

Figure 1: Visual representation of Carl Djerassi “teaching” Dendral (Photograph from: November, Joseph A. “Digitizing Life: The Introduction of Computers to Biology and Medicine.” Doctoral dissertation, Princeton University, 2006)

Image:November2.jpg

Figure 2: Visual representation of how Dendral works without an expert (Photograph from: November, Joseph A. “Digitizing Life: The Introduction of Computers to Biology and Medicine.” Doctoral dissertation, Princeton University, 2006)

Furthermore, Bruce Buchanan was recruited by the Dendral team to refine Feigenbaum’s LISP programming code [36]. Buchanan possessed similar ideas and interests as both Feigenbaum and Lederberg, but his special interest was hypothesis formation [37]. As Joseph November in Digitizing Life: The Introduction of Computers to Biology and Medicine said, “He (Buchanan) wanted the system (Dendral) to make discoveries on its own, not just help humans make them.” Buchanan designed “Meta-Dendral,” which was a “hypothesis maker” [38]. Meta-Dendral and Dendral were fused together in 1966-67, and the next iteration was called the “Heuristic Dendral” [39]. The prime difference was that Heuristic Dendral “would serve as a template for similar systems in other areas” rather than just concentrating in the field of organic chemistry [40].


[edit] Applications of Dendral

Dendral was primarily used by organic chemists to solve structure elucidation problems by analyzing mass spectrometer graphs [41]. However, many other systems derived from the basis of Dendral. Some of the examples of those systems include: MYCIN, MOLGEN, MACSYMA, PROSPECTOR, XCON, and STEAMER.

[edit] Notes

  1. ^ Berk, 1985
  2. ^ Lindsay et al., 1980
  3. ^ Lindsay et al., 1980
  4. ^ Lederberg, 1987
  5. ^ November, 2006
  6. ^ November, 2006
  7. ^ Lindsay et al., 1980
  8. ^ November, 2006
  9. ^ Lindsay et al., 1980
  10. ^ November, 2006
  11. ^ Lindsay et al., 1980
  12. ^ November, 2006
  13. ^ Lindsay et al., 1980
  14. ^ Lindsay et al., 1980
  15. ^ Lindsay et al., 1980
  16. ^ Lindsay et al., 1980
  17. ^ Lindsay et al., 1980
  18. ^ Lindsay et al., 1980
  19. ^ Lindsay et al., 1980
  20. ^ Lindsay et al., 1980
  21. ^ Lindsay et al., 1980
  22. ^ Lindsay et al., 1980
  23. ^ Lindsay et al., 1980
  24. ^ Lindsay et al., 1980
  25. ^ November, 2006
  26. ^ November, 2006
  27. ^ Lederberg, 1963
  28. ^ November, 2006
  29. ^ November, 2006
  30. ^ November, 2006
  31. ^ November, 2006
  32. ^ November, 2006
  33. ^ November, 2006
  34. ^ November, 2006
  35. ^ November, 2006
  36. ^ November, 2006
  37. ^ November, 2006
  38. ^ November, 2006
  39. ^ November, 2006
  40. ^ November, 2006
  41. ^ November, 2006

[edit] References

[edit] Primary Sources

  1. Berk, A A. LISP: the Language of Artificial Intelligence. New York: Van Nostrand Reinhold Company, 1985. 1-25.
  2. Lederberg, Joshua. An Instrumentation Crisis in Biology. Stanford University Medical School. Palo Alto, 1963.
  3. Lederberg, Joshua. How Dendral Was Conceived and Born. ACM Symposium on the History of Medical Informatics, 05 Nov. 1987, Rockefeller University. New York: National Library of Medicine, 1987.
  4. Lindsay, Robert K., Bruce G. Buchanan, Edward A. Feigenbaum, and Joshua Lederberg. Applications of Artificial Intelligence for Organic Chemistry: The Dendral Project. McGraw-Hill Book Company, 1980.
  5. November, Joseph A. “Digitizing Life: The Introduction of Computers to Biology and Medicine.” Doctoral dissertation, Princeton University, 2006.
Retrieved from "http://en.wikipedia.org../../../d/e/n/Dendral.html"
In other languages