Generator Matrix Based Search for Extremal Self-Dual Binary Error-Correcting Codes

Self-dual doubly even linear binary error-correcting codes, often referred to as Type II codes, are codes closely related to many combinatorial structures such as 5-designs. Extremal codes are codes that have the largest possible minimum distance for a given length and dimension. The existence of an extremal (72,36,16) Type II code is still open. Previous results show that the automorphism group of a putative code C with the aforementioned properties has order 5 or dividing 24. In this work, we present a method and the results of an exhaustive search showing that such a code C cannot admit an automorphism group Z6. In addition, we present so far unpublished construction of the extended Golay code by P. Becker. We generalize the notion and provide example of another Type II code that can be obtained in this fashion. Consequently, we relate Becker's construction to the construction of binary Type II codes from codes over GF(2^r) via the Gray map.

Using visual spatial search interface for WWW applications

Most Internet search engines are keyword-based. They are not efficient for the queries where geographical location is important, such as finding hotels within an area or close to a place of interest. A natural interface for spatial searching is a map, which can be used not only to display locations of search results but also to assist forming search conditions. A map-based search engine requires a well-designed visual interface that is intuitive to use yet flexible and expressive enough to support various types of spatial queries as well as aspatial queries. Similar to hyperlinks for text and images in an HTML page, spatial objects in a map should support hyperlinks. Such an interface needs to be scalable with the size of the geographical regions and the number of websites it covers. In spite of handling typically a very large amount of spatial data, a map-based search interface should meet the expectation of fast response time for interactive applications. In this paper we discuss general requirements and the design for a new map-based web search interface, focusing on integration with the WWW and visual spatial query interface. A number of current and future research issues are discussed, and a prototype for the University of Queensland is presented. (C) 2001 Published by Elsevier Science Ltd.

Evolutionary synthesis of stochastic gene network models using feature-based search spaces

A feature-based fitness function is applied in a genetic programming system to synthesize stochastic gene regulatory network models whose behaviour is defined by a time course of protein expression levels. Typically, when targeting time series data, the fitness function is based on a sum-of-errors involving the values of the fluctuating signal. While this approach is successful in many instances, its performance can deteriorate in the presence of noise. This thesis explores a fitness measure determined from a set of statistical features characterizing the time series' sequence of values, rather than the actual values themselves. Through a series of experiments involving symbolic regression with added noise and gene regulatory network models based on the stochastic 'if-calculus, it is shown to successfully target oscillating and non-oscillating signals. This practical and versatile fitness function offers an alternate approach, worthy of consideration for use in algorithms that evaluate noisy or stochastic behaviour.

The Salmon Algorithm - A New Population Based Search Metaheuristic

This thesis introduces the Salmon Algorithm, a search meta-heuristic which can be used for a variety of combinatorial optimization problems. This algorithm is loosely based on the path finding behaviour of salmon swimming upstream to spawn. There are a number of tunable parameters in the algorithm, so experiments were conducted to find the optimum parameter settings for different search spaces. The algorithm was tested on one instance of the Traveling Salesman Problem and found to have superior performance to an Ant Colony Algorithm and a Genetic Algorithm. It was then tested on three coding theory problems - optimal edit codes, optimal Hamming distance codes, and optimal covering codes. The algorithm produced improvements on the best known values for five of six of the test cases using edit codes. It matched the best known results on four out of seven of the Hamming codes as well as three out of three of the covering codes. The results suggest the Salmon Algorithm is competitive with established guided random search techniques, and may be superior in some search spaces.

Construction of a Festuca pratensis BAC library for map-based cloning in Festulolium substitution lines

Introgression in Festulolium is a potentially powerful tool to isolate genes for a large number of traits which differ between Festuca pratensis Huds. and Lolium perenne L. Not only are hybrids between the two species fertile, but the two genomes can be distinguished by genomic in situ hybridisation and a high frequency of recombination occurs between homoeologous chromosomes and chromosome segments. By a programme of introgression and a series of backcrosses, L. perenne lines have been produced which contain small F. pratensis substitutions. This material is a rich source of polymorphic markers targeted towards any trait carried on the F. pratensis substitution not observed in the L. perenne background. We describe here the construction of an F. pratensis BAC library, which establishes the basis of a map-based cloning strategy in L. perenne. The library contains 49,152 clones, with an average insert size of 112 kbp, providing coverage of 2.5 haploid genome equivalents. We have screened the library for eight amplified fragment length polymorphism (AFLP) derived markers known to be linked to an F. pratensis gene introgressed into L. perenne and conferring a staygreen phenotype as a consequence of a mutation in primary chlorophyll catabolism. While for four of the markers it was possible to identify bacterial artificial chromosome (BAC) clones, the other four AFLPs were too repetitive to enable reliable identification of locus-specific BACs. Moreover, when the four BACs were partially sequenced, no obvious coding regions could be identified. This contrasted to BACs identified using cDNA sequences, when multiple genes were identified on the same BAC.

A human-horse comparative map based on equine BAC end sequences

In an effort to increase the density of sequence-based markers for the horse genome we generated 9473 BAC end sequences (BESs) from the CHORI-241 BAC library with an average read length of 677 bp. BLASTN searches with the BESs revealed 4036 meaningful hits (E

An alternative pathway to β-carotene formation in plant chromoplasts discovered by map-based cloning of Beta and old-gold color mutations in tomato

Carotenoid pigments in plants fulfill indispensable functions in photosynthesis. Carotenoids that accumulate as secondary metabolites in chromoplasts provide distinct coloration to flowers and fruits. In this work we investigated the genetic mechanisms that regulate accumulation of carotenoids as secondary metabolites during ripening of tomato fruits. We analyzed two mutations that affect fruit pigmentation in tomato (Lycopersicon esculentum): Beta (B), a single dominant gene that increases β-carotene in the fruit, and old-gold (og), a recessive mutation that abolishes β-carotene and increases lycopene. Using a map-based cloning approach we cloned the genes B and og. Molecular analysis revealed that B encodes a novel type of lycopene β-cyclase, an enzyme that converts lycopene to β-carotene. The amino acid sequence of B is similar to capsanthin-capsorubin synthase, an enzyme that produces red xanthophylls in fruits of pepper (Capsicum annum). Our results prove that β-carotene is synthesized de novo during tomato fruit development by the B lycopene cyclase. In wild-type tomatoes B is expressed at low levels during the breaker stage of ripening, whereas in the Beta mutant its transcription is dramatically increased. Null mutations in the gene B are responsible for the phenotype in og, indicating that og is an allele of B. These results confirm that developmentally regulated transcription is the major mechanism that governs lycopene accumulation in ripening fruits. The cloned B genes can be used in various genetic manipulations toward altering pigmentation and enhancing nutritional value of plant foods.

A Digital Library of Folklore Songs and Keyword-Based Search Engine

ACM Computing Classification System (1998): H3.3, H.5.5, J5.

Keyword Join: Realizing Keyword Search in P2P-based Database Systems

In this paper, we present a P2P-based database sharing system that provides information sharing capabilities through keyword-based search techniques. Our system requires neither a global schema nor schema mappings between different databases, and our keyword-based search algorithms are robust in the presence of frequent changes in the content and membership of peers. To facilitate data integration, we introduce keyword join operator to combine partial answers containing different keywords into complete answers. We also present an efficient algorithm that optimize the keyword join operations for partial answer integration. Our experimental study on both real and synthetic datasets demonstrates the effectiveness of our algorithms, and the efficiency of the proposed query processing strategies.

A microsatellite-based, gene-rich linkage map for the AA genome of Arachis (Fabaceae)

Cultivated peanut (Arachis hypogaea) is an important crop, widely grown in tropical and subtropical regions of the world. It is highly susceptible to several biotic and abiotic stresses to which wild species are resistant. As a first step towards the introgression of these resistance genes into cultivated peanut, a linkage map based on microsatellite markers was constructed, using an F-2 population obtained from a cross between two diploid wild species with AA genome (A. duranensis and A. stenosperma). A total of 271 new microsatellite markers were developed in the present study from SSR-enriched genomic libraries, expressed sequence tags (ESTs), and by data-mining sequences available in GenBank. of these, 66 were polymorphic for cultivated peanut. The 271 new markers plus another 162 published for peanut were screened against both progenitors and 204 of these (47.1%) were polymorphic, with 170 codominant and 34 dominant markers. The 80 codominant markers segregating 1:2:1 (P < 0.05) were initially used to establish the linkage groups. Distorted and dominant markers were subsequently included in the map. The resulting linkage map consists of 11 linkage groups covering 1,230.89 cM of total map distance, with an average distance of 7.24 cM between markers. This is the first microsatellite-based map published for Arachis, and the first map based on sequences that are all currently publicly available. Because most markers used were derived from ESTs and genomic libraries made using methylation-sensitive restriction enzymes, about one-third of the mapped markers are genic. Linkage group ordering is being validated in other mapping populations, with the aim of constructing a transferable reference map for Arachis.

MOOGLE: a metamodel-based model search engine

Models are becoming increasingly important in the software development process. As a consequence, the number of models being used is increasing, and so is the need for efficient mechanisms to search them. Various existing search engines could be used for this purpose, but they lack features to properly search models, mainly because they are strongly focused on text-based search. This paper presents Moogle, a model search engine that uses metamodeling information to create richer search indexes and to allow more complex queries to be performed. The paper also presents the results of an evaluation of Moogle, which showed that the metamodel information improves the accuracy of the search.