Grant: Discovery Grants Program - Individual

When transmitting data, errors can occur due to noise. In binary data, these errors cause the value in a single bit to be changed from 0 to 1 or vice-versa. When using an error-correcting code, we store the data according to a specific pattern before transmitting it. After transmission, this pattern allows us to determine in which bits errors have occurred, and then to correct them. Traditional error-correcting codes, capable of correcting errors such as these, are used in many areas including for satellite transmissions and to store data on compact discs. Data is not always binary. In fact, data can also be stored in DNA, in which the logical counterpart to a ""bit"" is a ""base"" with four possible values. Also, other types of errors may occur: in biological applications, it is useful to correct insertions and deletions of symbols as well as substitutions. The related area of DNA computing uses the DNA itself to perform computations; using error-correcting codes improves reliability. Error-correcting codes do not exist for all possible sets of parameters. Thus if we wish to use a code of a certain type we may have to perform a search to determine if it exists and its structure. This is called a combinatorial search. Such searches typically have a huge search space, and thus the use of computers is generally a necessity. Combinatorial searches may be applied to many different types of structures, including weighing matrices and designs. Another example of their use is protein side-chain packing, which involves finding the best arrangement of a given protein; from a Computer Science point of view, this is often represented as another well-known combinatorial structure, a graph. The primary objectives of my research are to provide answers to the above types of problems, and furthermore to determine appropriate algorithms for use in different types of searches.