Haplotype block partitioning and tag SNP selection under the perfect phylogeny model

Single Nucleotide Polymorphisms [SNPs] are the most usual form of polymorphism in human genome. Analyses of genetic variations have revealed that individual genomes share common SNP-haplotypes. The particular pattern of these common variations forms a block-like structure on human genome. In this work, we develop a new method based on the Perfect Phylogeny Model to identify haplotype blocks using samples of individual genomes. We introduce a rigorous definition of the quality of the partitioning of haplotypes into blocks and devise a greedy algorithm for finding the proper partitioning in case of perfect and semi-perfect phylogeny. It is shown that the minimum number of tagSNPs in a haplotype block of Perfect Phylogeny can be obtained by a polynomial time algorithm. We compare the performance of our algorithm on haplotype data of human chromosome 21 with other previously developed methods through simulations. The results demonstrate that our algorithm outperforms the conventional implementation of the Four Gamete Test approach which is the only available method for haplotype block partitioning based on Perfect Phylogeny

Helix segment assignment in proteins using fuzzy logic

The automatic assignment of protein secondary structure from three dimensional coordinates is an essential step in the characterization of protein structure. Although, the recognition of secondary structures such as alpha-helices and beta-sheets seem straightforward, but there are many different definitions, each regarding different criteria. We have developed a new algorithm for protein helix assignment, by using fuzzy logic based on backbone torsion angles. In this method, each residue takes a number from 0 to 100 that indicates the helical membership degree of that residue. This method can be converted to a classical method whenever we assume that any residue with a membership degree greater than 83 is a helix. Comparison of the results with structures reported in protein data bank [PDB], dictionary of secondary structure of proteins [DSSP] and structure identification [STRIDE] for 324 proteins indicate that our algorithm works as well as DSSP showing 93% agreement. We believe that the fuzzy secondary structure assignment has more advantages than the other classical approaches used for protein structure comparisons and alignments