PubMed Health⌕ Search
Home/Archive/PubMed

PubMed · 11817100

Seriation of asymmetric matrices using integer linear programming.

M J Brusco
View original source ↗Export metadata ↓

Abstract

Integer linear programming approaches for seriation of asymmetric n x n proximity matrices have generally been perceived as intractable for problems of practical size. However, to date, no computational evidence has been provided regarding the effectiveness (or ineffectiveness) of such approaches. This paper presents an evaluation of an integer linear programming method for asymmetric seriation using five moderately sized matrices (15 < or = n < or = 36) from the psychological literature, as well as 80 synthetic matrices (20 < or = n < or = 30). The solution to the linear programming relaxation of the integer-programming model was integer-optimal for each of the five empirical matrices and many of the synthetic matrices. In such instances, branch-and-bound integer programming was not required and optimal orderings were obtained within a few seconds. In all cases where the solution to the linear programming relaxation was not integer-optimal, branch-and-bound integer programming was able to find an optimal seriation in 18 minutes or less. A pragmatic solution strategy for larger matrices (n > 30) is also presented. This approach exploits the fact that, in many instances, only a modest percentage of all possible transitivity constraints are required to obtain an optimal solution.

Explore related subjects

HumansMathematical ComputingProgramming, LinearPsychometricsResearchJournal Article

Keep this discovery

Explore connections, maps & timelines

BibTeXRIS

M J Brusco. 2001. Seriation of asymmetric matrices using integer linear programming.. https://doi.org/10.1348/000711001159500

Cite the original work for its findings. Save a collection to share your selection of sources.

KEEP EXPLORING

Related citations

PubMed2027

Global Genomic Surveillance.

Global genomic surveillance has emerged as a foundational pillar of public health in the twenty-first century, enabling real-time tracking of pathogen evolution and informing outbreak response. This chapter examines the strategic architecture of global genomic surveillance, focusing on its application to arboviruses such as chikungunya virus (CHIKV). It explores the integration of genomic data with epidemiological, clinical, and environmental information within a One Health framework, while addressing critical challenges in governance, equity, and interoperability. The discussion covers the entire genomic surveillance workflow, from sample collection and sequencing to bioinformatic analysis and phylogenetic inference, and highlights the transformative role of artificial intelligence (AI) in predictive surveillance. By analyzing global initiatives, operational barriers, and emerging technologies, this chapter underscores the necessity of sustainable, equitable, and interoperable genomic systems to proactively address current and future infectious disease threats.

Humans↗
PubMed2027

Systematic Dissection of Key Driver Perturbation Signatures in Single Cells via ECCITE-seq.

CRISPR screens, such as expanded CRISPR-compatible cellular indexing of transcriptomes and epitopes by sequencing (ECCITE-seq), enable the simultaneous measurement of transcriptomes, gRNA identity, and cell-surface protein expression at single-cell resolution to systematically interrogate gene function. This platform provides a powerful and scalable experimental approach for validating disease-associated regulators identified by large-scale association studies and other computational methods, including network-based analyses of multi-omics data. Here, as an example application, we describe an ECCITE-seq framework to characterize the transcriptomic consequences of perturbing multiple neuronal key driver genes associated with Alzheimer's disease (AD) in human-induced pluripotent stem cell (hiPSC)-derived neurons. More broadly, by integrating customized pooled gRNA libraries with different CRISPR effectors across multiple cell types, this approach allows for the assessment of the regulatory impact of candidate genes implicated in development and disease processes.

Humans↗
PubMed2027

Identification of Genome-Wide Chromatin Structural Aberration in Cancer by Hi-C Analysis.

Aberrant three-dimensional genome organization is a hallmark of cancer, often driving oncogene activation through mechanisms such as enhancer hijacking. High-throughput chromosome conformation capture (Hi-C) maps these interactions on a genome-wide scale. Unlike earlier dilution-based methods, in situ Hi-C performs proximity ligation within intact nuclei, minimizing random ligation noise and enabling fine-scale structure detection. This chapter describes an optimized in situ Hi-C protocol tailored for cancer cell lines using MboI digestion and biotin-mediated pull-down to generate high-complexity libraries. We further outline a computational workflow that extends beyond standard topological mapping of compartments and topologically associating domains to identify cancer-specific aberrations. Specifically, we focus on detecting chromosomal rearrangements (structural variants) and characterizing the distinct circular topology of extrachromosomal DNA. This integrated experimental and analytical framework provides the necessary tools to dissect the spatial dysregulation underlying tumor evolution.

Humans↗