BACKGROUND: The number of porcine Single Nucleotide Polymorphisms (SNPs) used in genetic association studies is very large, suitable for statistical testing. However, in breed classification problem, one needs to have a much smaller porcine-classifying SNPs (PCSNPs) set that could accurately classify pigs into different breeds. This study attempted to find such PCSNPs by using several combinations of feature selection and classification methods. We experimented with different combinations of feature selection methods including information gain, conventional as well as modified genetic algorithms, and our developed frequency feature selection method in combination with a common classification method, Support Vector Machine, to evaluate the method's performance. Experiments were conducted on a comprehensive data set containing SNPs from native pigs from America, Europe, Africa, and Asia including Chinese breeds, Vietnamese breeds, and hybrid breeds from Thailand. RESULTS: The best combination of feature selection methods-information gain, modified genetic algorithm, and frequency feature selection hybrid-was able to reduce the number of possible PCSNPs to only 1.62% (164 PCSNPs) of the total number of SNPs (10,210 SNPs) while maintaining a high classification accuracy (95.12%). Moreover, the near-identical performance of this PCSNPs set to those of bigger data sets as well as even the entire data set. Moreover, most PCSNPs were well-matched to a set of 94 genes in the PANTHER pathway, conforming to a suggestion by the Porcine Genomic Sequencing Initiative. CONCLUSIONS: The best hybrid method truly provided a sufficiently small number of porcine SNPs that accurately classified swine breeds.

BACKGROUND: Microscopic analysis requires that foreground objects of interest, e.g. cells, are in focus. In a typical microscopic specimen, the foreground objects may lie on different depths of field necessitating capture of multiple images taken at different focal planes. The extended depth of field (EDoF) technique is a computational method for merging images from different depths of field into a composite image with all foreground objects in focus. Composite images generated by EDoF can be applied in automated image processing and pattern recognition systems. However, current algorithms for EDoF are computationally intensive and impractical, especially for applications such as medical diagnosis where rapid sample turnaround is important. Since foreground objects typically constitute a minor part of an image, the EDoF technique could be made to work much faster if only foreground regions are processed to make the composite image. We propose a novel algorithm called object-based extended depths of field (OEDoF) to address this issue. METHODS: The OEDoF algorithm consists of four major modules: 1) color conversion, 2) object region identification, 3) good contrast pixel identification and 4) detail merging. First, the algorithm employs color conversion to enhance contrast followed by identification of foreground pixels. A composite image is constructed using only these foreground pixels, which dramatically reduces the computational time. RESULTS: We used 250 images obtained from 45 specimens of confirmed malaria infections to test our proposed algorithm. The resulting composite images with all in-focus objects were produced using the proposed OEDoF algorithm. We measured the performance of OEDoF in terms of image clarity (quality) and processing time. The features of interest selected by the OEDoF algorithm are comparable in quality with equivalent regions in images processed by the state-of-the-art complex wavelet EDoF algorithm; however, OEDoF required four times less processing time. CONCLUSIONS: This work presents a modification of the extended depth of field approach for efficiently enhancing microscopic images. This selective object processing scheme used in OEDoF can significantly reduce the overall processing time while maintaining the clarity of important image features. The empirical results from parasite-infected red cell images revealed that our proposed method efficiently and effectively produced in-focus composite images. With the speed improvement of OEDoF, this proposed algorithm is suitable for processing large numbers of microscope images, e.g., as required for medical diagnosis.

BACKGROUND: Epidermal growth factor receptor (EGFR) signalling plays a major role in biological processes, including cell proliferation, differentiation and survival. Since the over-expression of EGFR causes human cancers, EGFR is an attractive drug target. A tumor suppressor endogenous protein, MIG-6, is known to suppress EGFR over-expression by binding to the C-lobe of EGFR kinase. Thus, this C-lobe of the EGFR kinase is a potential new target for EGFR kinase activity inhibition. In this study, molecular dynamics (MD) simulations and binding free energy calculations were used to investigate the protein-peptide interactions between EGFR kinase and a 27-residue peptide derived from MIG-6_s1 segment (residues 336-362). RESULTS: These 27 residues of MIG-6_s1 were modeled from the published MIG-6 X-ray structure. The binding dynamics were detailed by applying the molecular mechanics Poisson-Boltzmann surface area (MM-PBSA) method to predict the binding free energy. Both van der Waals interactions and non-polar solvation were favorable driving forces for binding process. Six residues of EGFR kinase and eight residues of MIG-6_s1 residues were shown to be responsible for interface binding in which we investigated per residue free energy decomposition and the results from the computational alanine scanning approach. These residues also had higher hydrogen bond occupancies than other residues at the binding interface. The results from the aforementioned calculations reasonably agreed with the previous experimental mutagenesis studies. CONCLUSIONS: Molecular dynamics simulations were used to investigate the interactions of MIG-6_s1 to EGFR kinase domain. Our study provides an insight into such interactions that is useful in guiding the design of novel anticancer therapeutics. The information on our modelled peptide interface with EGFR kinase could be a possible candidate for an EGFR dimerization inhibitor.

BACKGROUND: Human epidermal growth factor receptor 2 (HER2) has an important role in cancer aggressiveness and poor prognosis. HER2 has been used as a drug target for cancers. In particular, to effectively treat HER2-positive cancer, small molecule inhibitors were developed to target HER2 kinase. Knowing that curcumin has been used as food to inhibit cancer activity, this study evaluated the efficacy of natural curcumins and curcumin analogs as HER2 inhibitors using in vitro and in silico studies. The curcumin analogs considered in this study composed of 4 groups classified by their core structure, β-diketone, monoketone, pyrazole, and isoxazole. RESULTS: In the present study, both computational and experimental studies were performed. The specificity of curcumin analogs selected from the docked results was examined against human breast cancer cell lines. The screened curcumin compounds were then subjected to molecular dynamics simulation study. By modifying curcumin analogs, we found that protein-ligand affinity increases. The benzene ring with a hydroxyl group could enhance affinity by forming hydrophobic interactions and the hydrogen bond with the hydrophobic pocket. Hydroxyl, carbonyl or methoxy group also formed hydrogen bonds with residues in the adenine pocket and sugar pocket of HER2-TK. These modifications could suggest the new drug design for potentially effective HER2-TK inhibitors. Two outstanding compounds, bisdemethylcurcumin (AS-KTC006) and 3,5-bis((E)-3,4-dimethoxystyryl)isoxazole (AS-KTC021 ),were well oriented in the binding pocket almost in the simulation time, 30 ns. This evidence confirmed the results of cell-based assays and the docking studies. They possessed more distinguished interactions than known HER2-TK inhibitors, considering them as a promising drug in the near future. CONCLUSIONS: The series of curcumin compounds were screened using a computational molecular docking and followed by human breast cancer cell lines assay. Both AS-KTC006 and AS-KTC021 could inhibit breast cancer cell lines though inhibiting of HER2-TK. The intermolecular interactions were confirmed by molecular dynamics simulation studies. This information would explore more understanding of curcuminoid structures and HER2-TK.

Understanding genetic differences among populations is one of the most important issues in population genetics. Genetic variations, e.g., single nucleotide polymorphisms, are used to characterize commonality and difference of individuals from various populations. This paper presents an efficient graph-based clustering framework which operates iteratively on the Neighbor-Joining (NJ) tree called the iNJclust algorithm. The framework uses well-known genetic measurements, namely the allele-sharing distance, the neighbor-joining tree, and the fixation index. The behavior of the fixation index is utilized in the algorithm's stopping criterion. The algorithm provides an estimated number of populations, individual assignments, and relationships between populations as outputs. The clustering result is reported in the form of a binary tree, whose terminal nodes represent the final inferred populations and the tree structure preserves the genetic relationships among them. The clustering performance and the robustness of the proposed algorithm are tested extensively using simulated and real data sets from bovine, sheep, and human populations. The result indicates that the number of populations within each data set is reasonably estimated, the individual assignment is robust, and the structure of the inferred population tree corresponds to the intrinsic relationships among populations within the data.

BACKGROUND: Identification of good metaphase spreads is an important step in chromosome analysis for identifying individuals with genetic disorders. The process of finding suitable metaphase chromosomes for accurate clinical analysis is, however, very time consuming since they are selected manually. The selection of suitable metaphase chromosome spreads thus represents a major bottleneck for conventional cytogenetic analysis. Although many algorithms have been developed for karyotyping, none have adequately addressed the critical bottleneck of selecting suitable chromosome spreads. In this paper, we present a software tool that uses a simple rule-based system to efficiently identify metaphase spreads suitable for karyotyping. RESULTS: The chromosome shapes can be classified by the software into four main classes. The first and the second classes refer to individual chromosomes with straight and skewed shapes, respectively. The third class is characterized as those chromosomes with overlapping bodies and the fourth class is for the non-chromosome objects. Good metaphase spreads should largely contain chromosomes of the first and the second classes, while the third class should be kept minimal. Several image parameters were examined and used for creating rule-based classification. The threshold value for each parameter is determined using a statistical model. We observed that the Gaussian model can represent the empirical probability density function of the parameters and, hence, the threshold value can be easily determined. The proposed rules can efficiently and accurately classify the individual chromosome with > 90% accuracy. CONCLUSIONS: The software tool, termed MetaSel, was developed. Using the Gaussian-based rules, the tool can be used to quickly rank hundreds of chromosome spread images so as to assist cytogeneticists to perform karyotyping effectively. Furthermore, MetaSel offers an intuitive, yet comprehensive, workflow to assist karyotyping, including tools for editing chromosome (split, merge and fix) and a karyotyping editor (moving, rotating, and pairing homologous chromosomes). The program can be freely downloaded from "http://www4a.biotec.or.th/GI/tools/metasel".

BACKGROUND: Current malaria diagnosis relies primarily on microscopic examination of Giemsa-stained thick and thin blood films. This method requires vigorously trained technicians to efficiently detect and classify the malaria parasite species such as Plasmodium falciparum (Pf) and Plasmodium vivax (Pv) for an appropriate drug administration. However, accurate classification of parasite species is difficult to achieve because of inherent technical limitations and human inconsistency. To improve performance of malaria parasite classification, many researchers have proposed automated malaria detection devices using digital image analysis. These image processing tools, however, focus on detection of parasites on thin blood films, which may not detect the existence of parasites due to the parasite scarcity on the thin blood film. The problem is aggravated with low parasitemia condition. Automated detection and classification of parasites on thick blood films, which contain more numbers of parasite per detection area, would address the previous limitation. RESULTS: The prototype of an automatic malaria parasite identification system is equipped with mountable motorized units for controlling the movements of objective lens and microscope stage. This unit was tested for its precision to move objective lens (vertical movement, z-axis) and microscope stage (in x- and y-horizontal movements). The average precision of x-, y- and z-axes movements were 71.481 ± 7.266 μm, 40.009 ± 0.000 μm, and 7.540 ± 0.889 nm, respectively. Classification of parasites on 60 Giemsa-stained thick blood films (40 blood films containing infected red blood cells and 20 control blood films of normal red blood cells) was tested using the image analysis module. By comparing our results with the ones verified by trained malaria microscopists, the prototype detected parasite-positive and parasite-negative blood films at the rate of 95% and 68.5% accuracy, respectively. For classification performance, the thick blood films with Pv parasite was correctly classified with the success rate of 75% while the accuracy of Pf classification was 90%. CONCLUSIONS: This work presents an automatic device for both detection and classification of malaria parasite species on thick blood film. The system is based on digital image analysis and featured with motorized stage units, designed to easily be mounted on most conventional light microscopes used in the endemic areas. The constructed motorized module could control the movements of objective lens and microscope stage at high precision for effective acquisition of quality images for analysis. The analysis program could accurately classify parasite species, into Pf or Pv, based on distribution of chromatin size.

Ten years ago when Asia-Pacific Bioinformatics Network held the first International Conference on Bioinformatics (InCoB) in Bangkok its theme was North-South Networking. At that time InCoB aimed to provide biologists and bioinformatics researchers in the Asia-Pacific region a forum to meet, interact with, and disseminate knowledge about the burgeoning field of bioinformatics. Meanwhile InCoB has evolved into a major regional bioinformatics conference that attracts not only talented and established scientists from the region but increasingly also from East Asia, North America and Europe. Since 2006 InCoB yielded 114 articles in BMC Bioinformatics supplement issues that have been cited nearly 1,000 times to date. In part, these developments reflect the success of bioinformatics education and continuous efforts to integrate and utilize bioinformatics in biotechnology and biosciences in the Asia-Pacific region. A cross-section of research leading from biological data to knowledge and to technological applications, the InCoB2012 theme, is introduced in this editorial. Other highlights included sessions organized by the Pan-Asian Pacific Genome Initiative and a Machine Learning in Immunology competition. InCoB2013 is scheduled for September 18-21, 2013 at Suzhou, China.

An extension of principal component analysis called ip-PCA has been proposed earlier for analyzing structure in genetic data. This non-parametric framework iteratively classifies individuals into subpopulations. However, it is prone to false positives when dealing with large datasets and mixed-type genetic markers. We address these shortcomings by introducing a unified encoding scheme and suggesting a new terminating criterion for ipPCA. To validate the improvements, simulated datasets as well as real bovine and large human genetic datasets are analyzed. It is observed that the estimation of the number of subpopulations and the individual assignment accuracy have been improved. Furthermore, the structure resolved by this approach can be used to identify subset of individuals for further parametric population structure analysis.

BACKGROUND: The ever increasing sizes of population genetic datasets pose great challenges for population structure analysis. The Tracy-Widom (TW) statistical test is widely used for detecting structure. However, it has not been adequately investigated whether the TW statistic is susceptible to type I error, especially in large, complex datasets. Non-parametric, Principal Component Analysis (PCA) based methods for resolving structure have been developed which rely on the TW test. Although PCA-based methods can resolve structure, they cannot infer ancestry. Model-based methods are still needed for ancestry analysis, but they are not suitable for large datasets. We propose a new structure analysis framework for large datasets. This includes a new heuristic for detecting structure and incorporation of the structure patterns inferred by a PCA method to complement STRUCTURE analysis. RESULTS: A new heuristic called EigenDev for detecting population structure is presented. When tested on simulated data, this heuristic is robust to sample size. In contrast, the TW statistic was found to be susceptible to type I error, especially for large population samples. EigenDev is thus better-suited for analysis of large datasets containing many individuals, in which spurious patterns are likely to exist and could be incorrectly interpreted as population stratification. EigenDev was applied to the iterative pruning PCA (ipPCA) method, which resolves the underlying subpopulations. This subpopulation information was used to supervise STRUCTURE analysis to infer patterns of ancestry at an unprecedented level of resolution. To validate the new approach, a bovine and a large human genetic dataset (3945 individuals) were analyzed. We found new ancestry patterns consistent with the subpopulations resolved by ipPCA. CONCLUSIONS: The EigenDev heuristic is robust to sampling and is thus superior for detecting structure in large datasets. The application of EigenDev to the ipPCA algorithm improves the estimation of the number of subpopulations and the individual assignment accuracy, especially for very large and complex datasets. Furthermore, we have demonstrated that the structure resolved by this approach complements parametric analysis, allowing a much more comprehensive account of population structure. The new version of the ipPCA software with EigenDev incorporated can be downloaded from http://www4a.biotec.or.th/GI/tools/ippca.

BACKGROUND: Non-random patterns of genetic variation exist among individuals in a population owing to a variety of evolutionary factors. Therefore, populations are structured into genetically distinct subpopulations. As genotypic datasets become ever larger, it is increasingly difficult to correctly estimate the number of subpopulations and assign individuals to them. The computationally efficient non-parametric, chiefly Principal Components Analysis (PCA)-based methods are thus becoming increasingly relied upon for population structure analysis. Current PCA-based methods can accurately detect structure; however, the accuracy in resolving subpopulations and assigning individuals to them is wanting. When subpopulations are closely related to one another, they overlap in PCA space and appear as a conglomerate. This problem is exacerbated when some subpopulations in the dataset are genetically far removed from others. We propose a novel PCA-based framework which addresses this shortcoming. RESULTS: A novel population structure analysis algorithm called iterative pruning PCA (ipPCA) was developed which assigns individuals to subpopulations and infers the total number of subpopulations present. Genotypic data from simulated and real population datasets with different degrees of structure were analyzed. For datasets with simple structures, the subpopulation assignments of individuals made by ipPCA were largely consistent with the STRUCTURE, BAPS and AWclust algorithms. On the other hand, highly structured populations containing many closely related subpopulations could be accurately resolved only by ipPCA, and not by other methods. CONCLUSION: The algorithm is computationally efficient and not constrained by the dataset complexity. This systematic subpopulation assignment approach removes the need for prior population labels, which could be advantageous when cryptic stratification is encountered in datasets containing individuals otherwise assumed to belong to a homogenous population.

UNLABELLED: Bioinformatics involves the collection, organization and analysis of large amounts of biological data, using networks of computers and databases. Developing countries in the Asia-Pacific region are just moving into this new field of information-based biotechnology. However, the computational infrastructure and network bandwidths available in these countries are still at a basic level compared to that in developed countries. In this study, we assessed the utility of a BitTorrent-based Peer-to-Peer (btP2P) file distribution model for automatic synchronization and distribution of large amounts of biological data among developing countries. The initial country-level nodes in the Asia-Pacific region comprised Thailand, Korea and Singapore. The results showed a significant improvement in download performance using btP2P--three times faster overall download performance than conventional File Transfer Protocol (FTP). This study demonstrated the reliability of btP2P in the dissemination of continuously growing multi-gigabyte biological databases across the three Asia-Pacific countries. The download performance for btP2P can be further improved by including more nodes from other countries into the network. This suggests that the btP2P technology is appropriate for automatic synchronization and distribution of biological databases and software over low-bandwidth networks among developing countries in the Asia-Pacific region. AVAILABILITY: http://everest.bic.nus.edu.sg/p2p/

BACKGROUND: Single nucleotide polymorphisms (SNPs) are the most commonly studied units of genetic variation. The discovery of such variation may help to identify causative gene mutations in monogenic diseases and SNPs associated with predisposing genes in complex diseases. Accurate detection of SNPs requires software that can correctly interpret chromatogram signals to nucleotides. RESULTS: We present VarDetect, a stand-alone nucleotide variation exploratory tool that automatically detects nucleotide variation from fluorescence based chromatogram traces. Accurate SNP base-calling is achieved using pre-calculated peak content ratios, and is enhanced by rules which account for common sequence reading artifacts. The proposed software tool is benchmarked against four other well-known SNP discovery software tools (PolyPhred, novoSNP, Genalys and Mutation Surveyor) using fluorescence based chromatograms from 15 human genes. These chromatograms were obtained from sequencing 16 two-pooled DNA samples; a total of 32 individual DNA samples. In this comparison of automatic SNP detection tools, VarDetect achieved the highest detection efficiency. AVAILABILITY: VarDetect is compatible with most major operating systems such as Microsoft Windows, Linux, and Mac OSX. The current version of VarDetect is freely available at http://www.biotec.or.th/GI/tools/vardetect.

With a wealth of biodiversity, a long tradition of agriculture-based industries, and an established medical and biotechnological research and development community, Thailand has become an attractive location for life sciences investment. The large amount of data generated in many areas of life sciences requires visualization, management, and analysis, principally through bioinformatics. To become successful, Thailand's research community should emphasize establishing core technologies, such as genomics and bioinformatics, to boost development of agriculture, food processing, and biomedical research. The Thai government realized the importance of this field and created a national policy to greatly increase Thailand's participation in bioinformatics and genomics, budgeting for specific development goals in research infrastructure, education, and sustainable human resources. Thailand has not lagged behind in bioinformatics research activity and recognizes the importance of bioinformatics through increased policy awareness, human resources development, and increased research activity involving genomic-scale data generation and computational analyses. Many applications of genomics and bioinformatics to biomedical research and development in Thailand have progressed substantially during the past few years, leading to successful applications in some specific local areas. However, the applications to other important areas, such as agriculture, are hampered by the limited availability of genomic sequence data and the lack of necessary biochemical/physiological information. With the advent of more and more genomic information in public databases, Thailand's research community is striving to adopt comparative genomics to obtain information of direct relevance to the country's health and industrial needs. This article highlights Thailand's contribution to genomics and bioinformatics in the following areas: (1) policy support from the Thai government, (2) capacity building through infrastructure/education/human resources, and (3) research and development in genomics and computational biology. (See Box 1 for Authors' Biographies). Box 1. Authors' Biographies Wannipha Tongsima, M.S., obtained her master's degree in Industrial Microbiology from Chulalongkorn University, Thailand. She was involved in founding the Bioinformatics research program in BIOTEC. To reinforce the research activity in this area, she also helped organize the first International Conference on Computational Biology (InCoB), held in Bangkok in 2002. Later, she was appointed to manage one of the first BIOTEC ethnic-specific human genetic variation programs, named the Thailand SNP Discovery Project. She works as a Genomic Medicine program coordinator for the Cluster and Program Management Office (CPMO) of the National Science and Technology Development Agency (NSTDA), which is an umbrella organization of four other national research centers in Thailand, including BIOTEC. Sissades Tongsima, Ph.D., received his doctoral degree in Computer Science and Engineering from the University of Notre Dame, Indiana, United States. He has worked for the National Electronics and Computer Technology Center on High Performance Computing (HPC) and Computational Grid. During 2002–2004, he cochaired the Asia-Pacific Advanced Network (APAN) Grid Working Group. In 2003, he shifted his research direction from HPC architecture to bioinformatics research, when he started working for BIOTEC, and constructed the ThaiSNP database. His main research interest is in developing algorithms and databases for analyzing various research projects on human genetic variation. He currently heads the Genome Institute biostatistics and informatics laboratory at BIOTEC. Prasit Palittapongarnpim, M.D., earned his medical degree from Mahidol University, Thailand, and his B.S. in Mathematics from Ramkumhang University, Thailand. He is a Fellow of the Royal College of Pediatricians of Thailand and also an Associate Professor in Microbiology at Mahidol University, where he has conducted research focusing on tuberculosis. While holding a Deputy Director position, he initiated the Bioinformatics research program at BIOTEC in 2002 and led the organization of the first InCoB conference in 2002. He is currently a Vice President of NSTDA.

ClustalW is the most widely used tool for aligning multiple protein or nucleotide sequences. The alignment is achieved via three stages: pairwise alignment, guide tree generation and progressive alignment. This paper analyzes and enhances a multithreaded implementation of ClustalW called ClustalW-SMP for higher throughput. Our goal is to maximize the degree of parallelism on multithreading ClustalW called MultiThreading-ClustalW (MT-ClustalW). As a result, bioinformatics laboratories are able to use this MT-ClustalW with much less energy consumption on multicore and SMP (symmetric multiprocessor) machines than that of PC clusters. The experiment results show that the MT-ClustalW framework can achieve a considerable speedup over the sequential ClustalW and original multithreaded ClustalW-SMP implementations

We propose an framework to estimate resource bounds. The framework takes imprecise system characteristics and multiple design attributes into account. Considering a design goal, an initial bound is first generated. Then, a polynomial-time process called inclusion scheduling is used as a tool to determine a schedule under impreciseness and improve the bounds. Our experiments show that considering impreciseness can achieve a better bound than the traditional approach.

One of the difficulties in high-level synthesis and compiler optimization is obtaining a good schedule without knowing the exact computation time of the tasks involved. The uncertain computation times of these tasks normally occur when conditional instructions are employed and/or inputs of the tasks influence the computation time. The relationship between these tasks can be represented as a data-flow graph where each node models the task associated with a probabilistic computation time. A set of edges represents the dependencies between tasks. In this research, we study scheduling and optimization algorithms taking into account the probabilistic execution times. Two novel algorithms, called probabilistic retiming and probabilistic rotation scheduling, are developed for solving the underlying nonresource and resource constrained scheduling problems, respectively. Experimental results show that probabilistic retiming consistently produces a graph with a smaller longest path computation time for a given confidence level, as compared with the traditional retiming algorithm that assumes a fixed worst-case and average-case computation times. Furthermore, when considering the resource constraints and probabilistic environments, probabilistic rotation scheduling gives a schedule whose length is guaranteed to satisfy a given probability requirement. This schedule is better than schedules produced by other algorithms that consider worst-case and average-case scenarios.

Many iterative or recursive applications commonly found in DSP and image processing applications can be represented by data-flow graphs (DFGs). This graph is then used to perform DFG scheduling, where the starting times for executing the application's individual tasks are determined. The minimum length of time required to execute all tasks once is called the schedule length of the DFG. A great deal of research has been done attempting to optimize such applications by applying various graph transformation techniques to the DFG in order to minimize this schedule length. One of the most effective of these techniques is retiming. We demonstrate that the traditional retiming technique does not always achieve optimal schedules and propose a new graph transformation technique, extended retiming, which will. We also present an algorithm for finding an extended retiming which transforms a DFG into one with minimal schedule length. Finally, we demonstrate a constant-time algorithm which verifies the existence of a retimed DFG with the minimum schedule length.

It is known that in many applications, because of selection statements, e.g., if-statement, the computation time of a node can be represented by a random variable. This paper focuses on any iterative application (containing loops) reflecting those uncertainties. Such an application can then be transformed to a probabilistic data-flow graph. A challenging problem is to derive graph transformation techniques which can produce a good schedule. This paper introduces two timing models, the time-invariant and time-variant models, to characterize the nature of these applications. Furthermore, for the time-invariant model, we propose a means of selecting a minimum rate-optimal unfolding factor which guarantees the best schedule length. We also propose a good estimation for choosing an unfolding factor for a graph under the time-variant model.

One of the biggest problems in high-level synthesis is to obtain a good schedule without the knowledge of exact computation time of tasks. While the target applications in high-level synthesis are becoming larger a task in the applications such as artificial intelligent systems or interface may have uncertain computation time. In this paper an algorithm to schedule these repetitive tasks and optimize the schedule is presented. A probabilistic data-flow graph is employed to model the problem where each node represents a task associated with the probabilistic computation time and a set of edges represents the dependences between the tasks. A novel polynomial-time probabilistic retiming algorithm for optimizing the graph and an algorithm for computing the optimized schedule, subject to the acceptable probability and resource constraint, are presented. The optimization algorithm also guarantees to give such a short schedule length with a given qualitatively provable, confidence level. The experiments show that the resulting schedule length for a given confidence probability can be significantly reduced.

This paper proposes an algorithm called probabilistic rotation scheduling which takes advantage of loop pipelining to schedule tasks with uncertain times to a parallel processing system. These tasks normally occur when conditional instructions are employed and/or inputs of the tasks influence the computation time. We show that based on our loop scheduling algorithm the length of the resulting schedule can be guaranteed to be satisfied for a given probability. The experiments show that the resulting schedule length for a given probability of confidence can be significantly better than the schedules obtained by worst-case or average-case scenario.

One of the common problems for fuzzy system implementation arises from the complications of the fuzzy inference process. Extra computations are required to deduce a consequence due to nature of fuzzy sets. Furthermore, considerable simulations need to be performed to verify system functions. In order to reduce the prototyping time, the fuzzy system is partitioned into hardware and software portions. The model, called Fuzzy Rule-based Automata (FRA), is proposed to simplify fuzzy rule base. Since most rule base are rarely changed, they can be implemented in hardware to speedup the running time. Special computations for inference process is taken care by software to reduce hardware complications which yields prototype flexibility.

While research on the static scheduling of computational tasks for parallel systems has been ongoing for years, most work does not consider the communication costs nor does it consider the network congestion. A new static scheduling technique is presented which focuses on the communication overhead inherent in parallel processing systems. This paper builds a framework based on a newly developed graph model called a collision graph to study this problem. Using this model, algorithms are developed which can be embedded into existing static scheduling methods to improve their performance. The scheduling of cyclic data flow graphs was shown to be improved significantly as this technique was applied to the cyclo-compaction scheduling algorithm.

Loop pipelining (retiming) is a valuable tool used to explore parallelism across iterations. Few results are available about loop pipelining with data communication considerations. This paper first designs a modified list scheduling algorithm to be used as a subroutine in a novel technique called "communication sensitive rotation scheduling". Such a technique explores loop pipelining properties while handling the underlying imposed communication environment. An initial schedule is transformed to a more compact one under resource constraints.>