Dataset Information

Efficient and accurate construction of genetic linkage maps from the minimum spanning tree of a graph.

ABSTRACT: Genetic linkage maps are cornerstones of a wide spectrum of biotechnology applications, including map-assisted breeding, association genetics, and map-assisted gene cloning. During the past several years, the adoption of high-throughput genotyping technologies has been paralleled by a substantial increase in the density and diversity of genetic markers. New genetic mapping algorithms are needed in order to efficiently process these large datasets and accurately construct high-density genetic maps. In this paper, we introduce a novel algorithm to order markers on a genetic linkage map. Our method is based on a simple yet fundamental mathematical property that we prove under rather general assumptions. The validity of this property allows one to determine efficiently the correct order of markers by computing the minimum spanning tree of an associated graph. Our empirical studies obtained on genotyping data for three mapping populations of barley (Hordeum vulgare), as well as extensive simulations on synthetic data, show that our algorithm consistently outperforms the best available methods in the literature, particularly when the input data are noisy or incomplete. The software implementing our algorithm is available in the public domain as a web tool under the name MSTmap.

SUBMITTER: Wu Y

PROVIDER: S-EPMC2556103 | biostudies-literature | 2008 Oct

REPOSITORIES: biostudies-literature

ACCESS DATA

Publications

Efficient and accurate construction of genetic linkage maps from the minimum spanning tree of a graph.

Wu Yonghui Y Bhat Prasanna R PR Close Timothy J TJ Lonardi Stefano S

PLoS genetics 20081010 10

Genetic linkage maps are cornerstones of a wide spectrum of biotechnology applications, including map-assisted breeding, association genetics, and map-assisted gene cloning. During the past several years, the adoption of high-throughput genotyping technologies has been paralleled by a substantial increase in the density and diversity of genetic markers. New genetic mapping algorithms are needed in order to efficiently process these large datasets and accurately construct high-density genetic map ...[more]

PMID: 18846212

Similar Datasets

Project description:Identifying early and non-invasive biomarkers to detect individuals in the earliest stages of the Alzheimer's disease continuum is crucial. As a result, electrophysiology and plasma biomarkers are emerging as great candidates in this pursuit due to their low invasiveness. This is the first magnetoencephalography study to assess the relationship between minimum spanning tree parameters, an alternative to overcome the comparability and thresholding problem issues characteristic of conventional brain network analyses, and plasma phosphorylated tau231 levels in unimpaired individuals, with different risk levels of Alzheimer's disease. Seventy-six individuals with available magnetoencephalography recordings and phosphorylated tau231 plasma determination were included. The minimum spanning tree for the theta, alpha and beta bands for each subject was obtained, and the leaf fraction, tree hierarchy and diameter were calculated. To study the relationship between these topological parameters and phosphorylated tau231, we performed correlation analyses, for the whole sample and considering the two risk sub-groups separately. Increasing concentrations of phosphorylated tau231 were associated with greater leaf fraction and tree hierarchy values, along with lower diameter values, for the alpha and theta frequency bands. These results emerged for the whole sample and the higher risk group, but not for the lower risk group. Our results indicate that the network topology of cognitively unimpaired individuals with elevated plasma phosphorylated tau231 levels, a marker of Alzheimer's disease pathology and amyloid-β accumulation, is already altered, shifting towards a more integrated network increasing its vulnerability and hub-dependency, mostly in the alpha band. This is indicated by increases in leaf fraction and tree hierarchy, along with reductions in diameter. These results match the initial trajectory proposed by theoretical models of disease progression and network disruption and suggest that changes in brain function and organization begin early on.

Project description:B cell receptor (BCR) genes exposed to an antigen undergo somatic hypermutations and Darwinian antigen selection, generating a large BCR-antibody diversity. This process, known as B cell affinity maturation, increases antibody affinity, forming a specific B cell lineage that includes the unmutated ancestor and mutated variants. In a B cell lineage, cells with a higher antigen affinity will undergo clonal expansion, while those with a lower affinity will not proliferate and probably be eliminated. Therefore, cellular (genotype) abundance provides a valuable perspective on the ongoing evolutionary process. Phylogenetic tree inference is often used to reconstruct B cell lineage trees and represents the evolutionary dynamic of BCR affinity maturation. However, such methods should process B-cell population data derived from experimental sampling that might contain different cellular abundances. There are a few phylogenetic methods for tracing the evolutionary events occurring in B cell lineages; best-performing solutions are time-demanding and restricted to analysing a reduced number of sequences, while time-efficient methods do not consider cellular abundances. We propose ClonalTree, a low-complexity and accurate approach to construct B-cell lineage trees that incorporates genotype abundances into minimum spanning tree (MST) algorithms. Using both simulated and experimental data, we demonstrate that ClonalTree outperforms MST-based algorithms and achieves a comparable performance to a method that explores tree-generating space exhaustively. Furthermore, ClonalTree has a lower running time, being more convenient for building B-cell lineage trees from high-throughput BCR sequencing data, mainly in biomedical applications, where a lower computational time is appreciable. It is hundreds to thousands of times faster than exhaustive approaches, enabling the analysis of a large set of sequences within minutes or seconds and without loss of accuracy. The source code is freely available at github.com/julibinho/ClonalTree.

Project description:Functional brain networks have been shown to undergo fundamental changes associated with aging or schizophrenia. However, the mechanism of how these factors exert influences jointly or interactively on brain networks remains elusive. A unified recognition of connectomic alteration patterns was also hampered by heterogeneities in network construction and thresholding methods. Recently, an unbiased network representation method regardless of network thresholding, so called minimal spanning tree algorithm, has been applied to study the critical skeleton of the brain network. In this study, we aimed to use minimum spanning tree (MST) as an unbiased network reconstruction and employed structural equation modeling (SEM) to unravel intertwined relationships among multiple phenotypic and connectomic variables in schizophrenia. First, we examined global and local brain network properties in 40 healthy subjects and 40 schizophrenic patients aged 21-55 using resting-state functional magnetic resonance imaging (rs-fMRI). Global network alterations are measured by graph theoretical metrics of MSTs and a connectivity-transitivity two-dimensional approach was proposed to characterize nodal roles. We found that networks of schizophrenic patients exhibited a more star-like global structure compared to controls, indicating excessive integration, and a loss of regional transitivity in the dorsal frontal cortex (corrected p <.05). Regional analysis of MST network topology revealed that schizophrenia patients had more network hubs in frontal regions, which may be linked to the "overloading" hypothesis. Furthermore, using SEM, we found that the level of MST integration mediated the influence of age on negative symptom severity (indirect effect 95% CI [0.026, 0.449]). These findings highlighted an altered network skeleton in schizophrenia and suggested that aging-related enhancement of network integration may undermine functional specialization of distinct neural systems and result in aggravated schizophrenic symptoms.

Dataset Information

Efficient and accurate construction of genetic linkage maps from the minimum spanning tree of a graph.

Publications

Efficient and accurate construction of genetic linkage maps from the minimum spanning tree of a graph.

Similar Datasets

OmicsDI is part of the ELIXIR infrastructure

Tweets