bluuebunny/crossref_metadata_2025_split huggingface dataset:
Efficient genome ancestry inference in complex pedigrees with inbreeding
Authors: Liu Eric Yi , Zhang Qi , McMillan Leonard , de Villena Fernando Pardo-Manuel , Wang Wei 
Published: June 2010

Abstract
Motivation: High-density SNP data of model animal resources provides opportunities for fine-resolution genetic variation studies. These genetic resources are generated through a variety of breeding schemes that involve multiple generations of matings derived from a set of founder animals. In this article, we investigate the problem of inferring the most probable ancestry of resulting genotypes, given a set of founder genotypes. Due to computational difficulty, existing methods either handle only small pedigree data or disregard the pedigree structure. However, large pedigrees of model animal resources often contain repetitive substructures that can be utilized in accelerating computation.
Results: We present an accurate and efficient method that can accept complex pedigrees with inbreeding in inferring genome ancestry. Inbreeding is a commonly used process in generating genetically diverse and reproducible animals. It is often carried out for many generations and can account for most of the computational complexity in real-world model animal pedigrees. Our method builds a hidden Markov model that derives the ancestry probabilities through inbreeding process without explicit modeling in every generation. The ancestry inference is accurate and fast, independent of the number of generations, for model animal resources such as the Collaborative Cross (CC). Experiments on both simulated and real CC data demonstrate that our method offers comparable accuracy to those methods that build an explicit model of the entire pedigree, but much better scalability with respect to the pedigree size.
Contact: weiwang@cs.unc.edu
Multi-population GWA mapping via multi-task regularized regression
Authors: Puniyani Kriti , Kim Seyoung , Xing Eric P. 
Published: June 2010

Abstract
Motivation: Population heterogeneity through admixing of different founder populations can produce spurious associations in genome- wide association studies that are linked to the population structure rather than the phenotype. Since samples from the same population generally co-evolve, different populations may or may not share the same genetic underpinnings for the seemingly common phenotype. Our goal is to develop a unified framework for detecting causal genetic markers through a joint association analysis of multiple populations.
Results: Based on a multi-task regression principle, we present a multi-population group lasso algorithm using L1/L2-regularized regression for joint association analysis of multiple populations that are stratified either via population survey or computational estimation. Our algorithm combines information from genetic markers across populations, to identify causal markers. It also implicitly accounts for correlations between the genetic markers, thus enabling better control over false positive rates. Joint analysis across populations enables the detection of weak associations common to all populations with greater power than in a separate analysis of each population. At the same time, the regression-based framework allows causal alleles that are unique to a subset of the populations to be correctly identified. We demonstrate the effectiveness of our method on HapMap-simulated and lactase persistence datasets, where we significantly outperform state of the art methods, with greater power for detecting weak associations and reduced spurious associations.
Availability: Software will be available at http://www.sailing.cs.cmu.edu/
Contact: epxing@cs.cmu.edu
Low-homology protein threading
Authors: Peng Jian , Xu Jinbo 
Published: June 2010

Abstract
Motivation: The challenge of template-based modeling lies in the recognition of correct templates and generation of accurate sequence-template alignments. Homologous information has proved to be very powerful in detecting remote homologs, as demonstrated by the state-of-the-art profile-based method HHpred. However, HHpred does not fare well when proteins under consideration are low-homology. A protein is low-homology if we cannot obtain sufficient amount of homologous information for it from existing protein sequence databases.
Results: We present a profile-entropy dependent scoring function for low-homology protein threading. This method will model correlation among various protein features and determine their relative importance according to the amount of homologous information available. When proteins under consideration are low-homology, our method will rely more on structure information; otherwise, homologous information. Experimental results indicate that our threading method greatly outperforms the best profile-based method HHpred and all the top CASP8 servers on low-homology proteins. Tested on the CASP8 hard targets, our threading method is also better than all the top CASP8 servers but slightly worse than Zhang-Server. This is significant considering that Zhang-Server and other top CASP8 servers use a combination of multiple structure-prediction techniques including consensus method, multiple-template modeling, template-free modeling and model refinement while our method is a classical single-template-based threading method without any post-threading refinement.
Contact: jinboxu@gmail.com
Fragment-free approach to protein folding using conditional neural fields
Authors: Zhao Feng , Peng Jian , Xu Jinbo 
Published: June 2010

AbstractMotivation: One of the major bottlenecks with ab initio protein folding is an effective conformation sampling algorithm that can generate native-like conformations quickly. The popular fragment assembly method generates conformations by restricting the local conformations of a protein to short structural fragments in the PDB. This method may limit conformations to a subspace to which the native fold does not belong because (i) a protein with really new fold may contain some structural fragments not in the PDB and (ii) the discrete nature of fragments may prevent them from building a native-like fold. Previously we have developed a conditional random fields (CRF) method for fragment-free protein folding that can sample conformations in a continuous space and demonstrated that this CRF method compares favorably to the popular fragment assembly method. However, the CRF method is still limited by its capability of generating conformations compatible with a sequence.Results: We present a new fragment-free approach to protein folding using a recently invented probabilistic graphical model conditional neural fields (CNF). This new CNF method is much more powerful than CRF in modeling the sophisticated protein sequence-structure relationship and thus, enables us to generate native-like conformations more easily. We show that when coupled with a simple energy function and replica exchange Monte Carlo simulation, our CNF method can generate decoys much better than CRF on a variety of test proteins including the CASP8 free-modeling targets. In particular, our CNF method can predict a correct fold for T0496_D1, one of the two CASP8 targets with truly new fold. Our predicted model for T0496 is significantly better than all the CASP8 models.Contact: jinboxu@gmail.com
Modularity and directionality in genetic interaction maps
Authors: Jaimovich Ariel , Rinott Ruty , Schuldiner Maya , Margalit Hanah , Friedman Nir 
Published: June 2010

AbstractMotivation: Genetic interactions between genes reflect functional relationships caused by a wide range of molecular mechanisms. Large-scale genetic interaction assays lead to a wealth of information about the functional relations between genes. However, the vast number of observed interactions, along with experimental noise, makes the interpretation of such assays a major challenge.Results: Here, we introduce a computational approach to organize genetic interactions and show that the bulk of observed interactions can be organized in a hierarchy of modules. Revealing this organization enables insights into the function of cellular machineries and highlights global properties of interaction maps. To gain further insight into the nature of these interactions, we integrated data from genetic screens under a wide range of conditions to reveal that more than a third of observed aggravating (i.e. synthetic sick/lethal) interactions are unidirectional, where one gene can buffer the effects of perturbing another gene but not vice versa. Furthermore, most modules of genes that have multiple aggravating interactions were found to be involved in such unidirectional interactions. We demonstrate that the identification of external stimuli that mimic the effect of specific gene knockouts provides insights into the role of individual modules in maintaining cellular integrity.Availability: We designed a freely accessible web tool that includes all our findings, and is specifically intended to allow effective browsing of our results (http://compbio.cs.huji.ac.il/GIAnalysis).Contact: maya.schuldiner@weizmann.ac.il; hanahm@ekmd.huji.ac.il; nir@cs.huji.ac.ilSupplementary information: Supplementary data are available at Bioinformatics online.
Close lower and upper bounds for the minimum reticulate network of multiple phylogenetic trees
Authors: Wu Yufeng 
Published: June 2010

AbstractMotivation: Reticulate network is a model for displaying and quantifying the effects of complex reticulate processes on the evolutionary history of species undergoing reticulate evolution. A central computational problem on reticulate networks is: given a set of phylogenetic trees (each for some region of the genomes), reconstruct the most parsimonious reticulate network (called the minimum reticulate network) that combines the topological information contained in the given trees. This problem is well-known to be NP-hard. Thus, existing approaches for this problem either work with only two input trees or make simplifying topological assumptions.Results: We present novel results on the minimum reticulate network problem. Unlike existing approaches, we address the fully general problem: there is no restriction on the number of trees that are input, and there is no restriction on the form of the allowed reticulate network. We present lower and upper bounds on the minimum number of reticulation events in the minimum reticulate network (and infer an approximately parsimonious reticulate network). A program called PIRN implements these methods, which also outputs a graphical representation of the inferred network. Empirical results on simulated and biological data show that our methods are practical for a wide range of data. More importantly, the lower and upper bounds match for many datasets (especially when the number of trees is small or reticulation level is low), and this allows us to solve the minimum reticulate network problem exactly for these datasets.Availability: A software tool, PIRN, is available for download from the web page: http://www.engr.uconn.edu/~ywu.Contact: ywu@engr.uconn.eduSupplementary information: Supplementary data is available at Bioinformatics online.
Phylogenetic networks do not need to be complex: using fewer reticulations to represent conflicting clusters
Authors: van Iersel Leo , Kelk Steven , Rupp Regula , Huson Daniel 
Published: June 2010

Abstract
Phylogenetic trees are widely used to display estimates of how groups of species are evolved. Each phylogenetic tree can be seen as a collection of clusters, subgroups of the species that evolved from a common ancestor. When phylogenetic trees are obtained for several datasets (e.g. for different genes), then their clusters are often contradicting. Consequently, the set of all clusters of such a dataset cannot be combined into a single phylogenetic tree. Phylogenetic networks are a generalization of phylogenetic trees that can be used to display more complex evolutionary histories, including reticulate events, such as hybridizations, recombinations and horizontal gene transfers. Here, we present the new Cass algorithm that can combine any set of clusters into a phylogenetic network. We show that the networks constructed by Cass are usually simpler than networks constructed by other available methods. Moreover, we show that Cass is guaranteed to produce a network with at most two reticulations per biconnected component, whenever such a network exists. We have implemented Cass and integrated it into the freely available Dendroscope software.
Contact: l.j.j.v.iersel@gmail.com
Supplementary information: Supplementary data are available at Bioinformatics online.
Time and memory efficient likelihood-based tree searches on phylogenomic alignments with missing data
Authors: Stamatakis Alexandros , Alachiotis Nikolaos 
Published: June 2010

Abstract
Motivation: The current molecular data explosion poses new challenges for large-scale phylogenomic analyses that can comprise hundreds or even thousands of genes. A property that characterizes phylogenomic datasets is that they tend to be gappy, i.e. can contain taxa with (many and disparate) missing genes. In current phylogenomic analyses, this type of alignment gappyness that is induced by missing data frequently exceeds 90%. We present and implement a generally applicable mechanism that allows for reducing memory footprints of likelihood-based [maximum likelihood (ML) or Bayesian] phylogenomic analyses proportional to the amount of missing data in the alignment. We also introduce a set of algorithmic rules to efficiently conduct tree searches via subtree pruning and re-grafting moves using this mechanism.
Results: On a large phylogenomic DNA dataset with 2177 taxa, 68 genes and a gappyness of 90%, we achieve a memory footprint reduction from 9 GB down to 1 GB, a speedup for optimizing ML model parameters of 11, and accelerate the Subtree Pruning Regrafting tree search phase by factor 16. Thus, our approach can be deployed to improve efficiency for the two most important resources, CPU time and memory, by up to one order of magnitude.
Availability: Current open-source version of RAxML v7.2.6 available at http://wwwkramer.in.tum.de/exelixis/software.html.
Contact: stamatak@cs.tum.edu
TRStalker: an efficient heuristic for finding fuzzy tandem repeats
Authors: Pellegrini Marco , Renda M. Elena , Vecchio Alessio 
Published: June 2010

AbstractMotivation: Genomes in higher eukaryotic organisms contain a substantial amount of repeated sequences. Tandem Repeats (TRs) constitute a large class of repetitive sequences that are originated via phenomena such as replication slippage and are characterized by close spatial contiguity. They play an important role in several molecular regulatory mechanisms, and also in several diseases (e.g. in the group of trinucleotide repeat disorders). While for TRs with a low or medium level of divergence the current methods are rather effective, the problem of detecting TRs with higher divergence (fuzzy TRs) is still open. The detection of fuzzy TRs is propaedeutic to enriching our view of their role in regulatory mechanisms and diseases. Fuzzy TRs are also important as tools to shed light on the evolutionary history of the genome, where higher divergence correlates with more remote duplication events.Results: We have developed an algorithm (christened TRStalker) with the aim of detecting efficiently TRs that are hard to detect because of their inherent fuzziness, due to high levels of base substitutions, insertions and deletions. To attain this goal, we developed heuristics to solve a Steiner version of the problem for which the fuzziness is measured with respect to a motif string not necessarily present in the input string. This problem is akin to the ‘generalized median string’ that is known to be an NP-hard problem. Experiments with both synthetic and biological sequences demonstrate that our method performs better than current state of the art for fuzzy TRs and that the fuzzy TRs of the type we detect are indeed present in important biological sequences.Availability: TRStalker will be integrated in the web-based TRs Discovery Service (TReaDS) at bioalgo.iit.cnr.it.Contact: marco.pellegrini@iit.cnr.itSupplementary information: Supplementary data are available at Bioinformatics online.
Automatic reconstruction of 3D neuron structures using a graph-augmented deformable model
Authors: Peng Hanchuan , Ruan Zongcai , Atasoy Deniz , Sternson Scott 
Published: June 2010

Abstract
Motivation: Digital reconstruction of 3D neuron structures is an important step toward reverse engineering the wiring and functions of a brain. However, despite a number of existing studies, this task is still challenging, especially when a 3D microscopic image has low single-to-noise ratio and discontinued segments of neurite patterns.
Results: We developed a graph-augmented deformable model (GD) to reconstruct (trace) the 3D structure of a neuron when it has a broken structure and/or fuzzy boundary. We formulated a variational problem using the geodesic shortest path, which is defined as a combination of Euclidean distance, exponent of inverse intensity of pixels along the path and closeness to local centers of image intensity distribution. We solved it in two steps. We first used a shortest path graph algorithm to guarantee that we find the global optimal solution of this step. Then we optimized a discrete deformable curve model to achieve visually more satisfactory reconstructions. Within our framework, it is also easy to define an optional prior curve that reflects the domain knowledge of a user. We investigated the performance of our method using a number of challenging 3D neuronal image datasets of different model organisms including fruit fly, Caenorhabditis elegans, and mouse. In our experiments, the GD method outperformed several comparison methods in reconstruction accuracy, consistency, robustness and speed. We further used GD in two real applications, namely cataloging neurite morphology of fruit fly to build a 3D ‘standard’ digital neurite atlas, and estimating the synaptic bouton density along the axons for a mouse brain.
Availability: The software is provided as part of the V3D-Neuron 1.0 package freely available at http://penglab.janelia.org/proj/v3d
Contact: pengh@janelia.hhmi.org
A statistical method for the detection of variants from next-generation resequencing of DNA pools
Authors: Bansal Vikas 
Published: June 2010

Abstract
Motivation: Next-generation sequencing technologies have enabled the sequencing of several human genomes in their entirety. However, the routine resequencing of complete genomes remains infeasible. The massive capacity of next-generation sequencers can be harnessed for sequencing specific genomic regions in hundreds to thousands of individuals. Sequencing-based association studies are currently limited by the low level of multiplexing offered by sequencing platforms. Pooled sequencing represents a cost-effective approach for studying rare variants in large populations. To utilize the power of DNA pooling, it is important to accurately identify sequence variants from pooled sequencing data. Detection of rare variants from pooled sequencing represents a different challenge than detection of variants from individual sequencing.
Results: We describe a novel statistical approach, CRISP [Comprehensive Read analysis for Identification of Single Nucleotide Polymorphisms (SNPs) from Pooled sequencing] that is able to identify both rare and common variants by using two approaches: (i) comparing the distribution of allele counts across multiple pools using contingency tables and (ii) evaluating the probability of observing multiple non-reference base calls due to sequencing errors alone. Information about the distribution of reads between the forward and reverse strands and the size of the pools is also incorporated within this framework to filter out false variants. Validation of CRISP on two separate pooled sequencing datasets generated using the Illumina Genome Analyzer demonstrates that it can detect 80–85% of SNPs identified using individual sequencing while achieving a low false discovery rate (3–5%). Comparison with previous methods for pooled SNP detection demonstrates the significantly lower false positive and false negative rates for CRISP.
Availability: Implementation of this method is available at http://polymorphism.scripps.edu/∼vbansal/software/CRISP/
Contact: vbansal@scripps.edu
Efficient construction of an assembly string graph using the FM-index
Authors: Simpson Jared T. , Durbin Richard 
Published: June 2010

AbstractMotivation: Sequence assembly is a difficult problem whose importance has grown again recently as the cost of sequencing has dramatically dropped. Most new sequence assembly software has started by building a de Bruijn graph, avoiding the overlap-based methods used previously because of the computational cost and complexity of these with very large numbers of short reads. Here, we show how to use suffix array-based methods that have formed the basis of recent very fast sequence mapping algorithms to find overlaps and generate assembly string graphs asymptotically faster than previously described algorithms.Results: Standard overlap assembly methods have time complexity O(N2), where N is the sum of the lengths of the reads. We use the Ferragina–Manzini index (FM-index) derived from the Burrows–Wheeler transform to find overlaps of length at least τ among a set of reads. As well as an approach that finds all overlaps then implements transitive reduction to produce a string graph, we show how to output directly only the irreducible overlaps, significantly shrinking memory requirements and reducing compute time to O(N), independent of depth. Overlap-based assembly methods naturally handle mixed length read sets, including capillary reads or long reads promised by the third generation sequencing technologies. The algorithms we present here pave the way for overlap-based assembly approaches to be developed that scale to whole vertebrate genome de novo assembly.Contact: js18@sanger.ac.uk
As-rigid-as-possible mosaicking and serial section registration of large ssTEM datasets
Authors: Saalfeld Stephan , Cardona Albert , Hartenstein Volker , Tomančák Pavel 
Published: June 2010

Abstract
Motivation: Tiled serial section Transmission Electron Microscopy (ssTEM) is increasingly used to describe high-resolution anatomy of large biological specimens. In particular in neurobiology, TEM is indispensable for analysis of synaptic connectivity in the brain. Registration of ssTEM image mosaics has to recover the 3D continuity and geometrical properties of the specimen in presence of various distortions that are applied to the tissue during sectioning, staining and imaging. These include staining artifacts, mechanical deformation, missing sections and the fact that structures may appear dissimilar in consecutive sections.
Results: We developed a fully automatic, non-rigid but as-rigid-as-possible registration method for large tiled serial section microscopy stacks. We use the Scale Invariant Feature Transform (SIFT) to identify corresponding landmarks within and across sections and globally optimize the pose of all tiles in terms of least square displacement of these landmark correspondences. We evaluate the precision of the approach using an artificially generated dataset designed to mimic the properties of TEM data. We demonstrate the performance of our method by registering an ssTEM dataset of the first instar larval brain of Drosophila melanogaster consisting of 6885 images.
Availability: This method is implemented as part of the open source software TrakEM2 (http://www.ini.uzh.ch/∼acardona/trakem2.html) and distributed through the Fiji project (http://pacific.mpi-cbg.de).
Contact: tomancak@mpi-cbg.de