{"metadata":{"kernelspec":{"language":"python","display_name":"Python 3","name":"python3"},"language_info":{"pygments_lexer":"ipython3","nbconvert_exporter":"python","version":"3.6.4","file_extension":".py","codemirror_mode":{"name":"ipython","version":3},"name":"python","mimetype":"text/x-python"}},"nbformat_minor":4,"nbformat":4,"cells":[{"cell_type":"markdown","source":"Domain Understanding
","metadata":{}},{"cell_type":"markdown","source":"In this notebook we will go through the *problem domain* related concepts, namely:\n\n1. **International Chemical Identifier** (InChI)\n2. **Levenshtein distance** - The problem metric","metadata":{}},{"cell_type":"markdown","source":"**As usual, please do remember to upvote if you like the content :)**","metadata":{}},{"cell_type":"markdown","source":"1. International Chemical Identifier (InChI)
","metadata":{}},{"cell_type":"markdown","source":"The IUPAC International Chemical Identifier (InChITM) is a non-proprietary identifier for chemical substances that can be used in printed and electronic data sources thus enabling easier linking of diverse data compilations. It was developed under IUPAC Project 2000-025-1-800 during the period 2000-2004.\n\nThe identifiers describe chemical substances in terms of layers of information — the atoms and their bond connectivity, tautomeric information, isotope information, stereochemistry, and electronic charge information.Not all layers have to be provided; for instance, the tautomer layer can be omitted if that type of information is not relevant to the particular application.\n\nIn order to avoid generating different InChIs for tautomeric structures, before generating the InChI, an input chemical structure is normalized to reduce it to its so-called core parent structure. This may involve changing bond orders, rearranging formal charges and possibly adding and removing protons. Different input structures may give the same result; for example, acetic acid and acetate would both give the same core parent structure, that of acetic acid. A core parent structure may be disconnected, consisting of more than one component, in which case the sublayers in the InChI usually consist of sublayers for each component, separated by semicolons (periods for the chemical formula sublayer.) One way this can happen is that all metal atoms are disconnected during normalization; so, for example, the InChI for tetraethyllead will have five components, one for lead and four for the ethyl groups.\n\nThe first, main, layer of the InChI refers to this core parent structure, giving its chemical formula, non-hydrogen connectivity without bond order (/c sublayer) and hydrogen connectivity (/h sublayer.) The /q portion of the charge layer gives its charge, and the /p portion of the charge layer tells how many protons (hydrogen ions) must be added to or removed from it to regenerate the original structure. If present, the stereochemical layer, with sublayers /b, /t, /m and /s, gives stereochemical information, and the isotopic layer /i (which may contain sublayers /h, /b, /t, /m and /s) gives isotopic information. These are the only layers which can occur in a standard InChI.\n\n\nEvery InChI starts with the string \"InChI=\" followed by the version number, currently 1. If the InChI is standard, this is followed by the letter S for standard InChIs, which is a fully standardized InChI flavor maintaining the same level of attention to structure details and the same conventions for drawing perception. The remaining information is structured as a sequence of layers and sub-layers, with each layer providing one specific type of information. The layers and sub-layers are separated by the delimiter \"/\" and start with a characteristic prefix letter (except for the chemical formula sub-layer of the main layer). The six layers with important sublayers are:\n\n**Main layer**\n\n1. Chemical formula (no prefix). This is the only sublayer that must occur in every InChI.\n a. Atom connections (prefix: \"c\"). The atoms in the chemical formula (except for hydrogens) are numbered in sequence; this sublayer describes which atoms are connected by bonds to which other ones.\n b. Hydrogen atoms (prefix: \"h\"). Describes how many hydrogen atoms are connected to each of the other atoms.\n\n2. Charge layer\n a. charge sublayer (prefix: \"q\")\n b. proton sublayer (prefix: \"p\" for \"protons\")\n\n3. Stereochemical layer\n a. double bonds and cumulenes (prefix: \"b\")\n b. tetrahedral stereochemistry of atoms and allenes (prefixes: \"t\", \"m\")\n c. type of stereochemistry information (prefix: \"s\")\n\n4. Isotopic layer (prefixes: \"i\", \"h\", as well as \"b\", \"t\", \"m\", \"s\" for isotopic stereochemistry)\n\n5. Fixed-H layer (prefix: \"f\"); contains some or all of the above types of layers except atom connections; may end with \"o\" sublayer; never included in standard InChI\n\n6. Reconnected layer (prefix: \"r\"); contains the whole InChI of a structure with reconnected metal atoms; never included in standard InChI\n","metadata":{}},{"cell_type":"markdown","source":"**Examples**","metadata":{}},{"cell_type":"markdown","source":"\n\n\nInChI=1S/C2H6O/c1-2-3/h3H,2H2,1H3","metadata":{}},{"cell_type":"markdown","source":"\n\nInChI=1S/C6H8O6/c7-1-2(8)5-3(9)4(10)6(11)12-5/h2,5,7-8,10-11H,1H2/t2-,5+/m0/s1","metadata":{}},{"cell_type":"markdown","source":"2. Levenshtein distance
","metadata":{}},{"cell_type":"markdown","source":"1. Levenshtein distance (LD) is a measure of the similarity between two strings, which we will refer to as the source string (s) and the target string (t). The distance is the number of deletions, insertions, or substitutions required to transform s into t. For example,\n\n2. If s is \"test\" and t is \"test\", then LD(s,t) = 0, because no transformations are needed. The strings are already identical.\n If s is \"test\" and t is \"tent\", then LD(s,t) = 1, because one substitution (change \"s\" to \"n\") is sufficient to transform s into t.\n\n3. The greater the Levenshtein distance, the more different the strings are.\n Levenshtein distance is named after the Russian scientist Vladimir Levenshtein, who devised the algorithm in 1965. If you can't spell or pronounce Levenshtein, the metric is also sometimes called edit distance.\n\n4. The Levenshtein distance algorithm has been used in:\n\n a. Spell checking\n\n b. Speech recognition\n\n c. DNA analysis\n\n d. Plagiarism detection\n","metadata":{}},{"cell_type":"markdown","source":"**The Algorithm**\n\n**Step 1** \n\nSet n to be the length of s.\nSet m to be the length of t.\nIf n = 0, return m and exit.\nIf m = 0, return n and exit.\nConstruct a matrix containing 0..m rows and 0..n columns.\n\n**Step 2** \n\nInitialize the first row to 0..n.\nInitialize the first column to 0..m.\n\n**Step 3** \n\nExamine each character of s (i from 1 to n).\n\n**Step 4** \n\nExamine each character of t (j from 1 to m).\n\n**Step 5** \n\nIf s[i] equals t[j], the cost is 0.\nIf s[i] doesn't equal t[j], the cost is 1.\n\n**Step 6**\n\nSet cell d[i,j] of the matrix equal to the minimum of:\na. The cell immediately above plus 1: d[i-1,j] + 1.\nb. The cell immediately to the left plus 1: d[i,j-1] + 1.\nc. The cell diagonally above and to the left plus the cost: d[i-1,j-1] + cost.\n\n**Step 7** \n\nAfter the iteration steps (3, 4, 5, 6) are complete, the distance is found in cell d[n,m].\n","metadata":{}},{"cell_type":"markdown","source":"**Example**","metadata":{}},{"cell_type":"markdown","source":"","metadata":{}},{"cell_type":"markdown","source":"","metadata":{}},{"cell_type":"markdown","source":"The distance is in the lower right hand corner of the matrix, i.e. **3**.","metadata":{}},{"cell_type":"markdown","source":"Please upvote if you liked the content and comment below if you have some inputs :)","metadata":{}},{"cell_type":"markdown","source":"**Sources**\n\n1. https://medium.com/@ethannam/understanding-the-levenshtein-distance-equation-for-beginners-c4285a5604f0\n2. https://people.cs.pitt.edu/~kirk/cs1501/assignments/editdistance/Levenshtein%20Distance.htm","metadata":{}}]}