NDLI: An improved algorithm for the sorting by reversals and transpositions problem

Please wait, while we are loading the content...

Extracting phylogenetic signals from multi-labeled gene trees and its significance for species tree construction

Couplet supertree by equivalence partitioning of taxa set and DAG formation

Dynamic networks reveal key players in aging

Big data challenges for estimating genome assembler quality

Simultaneous identification of robust synergistic subnetwork markers for effective cancer prognosis

Orientations of beta-strand traces and near maximum twist

An integrative framework for structure-based prediction of biological effects mediated by antipeptide antibodies

Incremental network querying in biological networks

Automatic biosystems comparison using semantic and name similarity

A schema-matching tool for Alzheimer's disease data integration

Automated ranking of stem cell colonies by translating biological rules to computational models

A multiscale hybrid evolutionary algorithm to obtain sample-based representations of multi-basin protein energy landscapes

Global network alignment in the context of aging

RNA-seq gene and transcript expression analysis using the BioExtract server and iPlant collaborative

Optimal cancer prognosis under network uncertainty

A computational model for data acquisition in SAXS

Development and validation of a broad scheme for prediction of HLA class II restricted T cell epitopes

On the impact of data integration and edge enrichment in mining significant signals from biological networks

Pheno2GRN: a workflow for phenotype to gene network study and reverse engineering comparison

The DOE systems biology knowledgebase (KBase): progress towards a system for collaborative and reproducible inference and modeling of biological function

Docking features for predicting binding loss due to protein mutation

Knowledge-based search and multi-objective filters: proposed structural models of GPCR dimerization

A powerful and robust co-expression network analysis algorithm

AlignMR: mass spectrometry peak alignment using Hadoop MapReduce

A novel context-sensitive random walk model for estimating node correspondence between two biological networks

Variational Bayesian clustering on protein cavity conformations for detecting influential amino acids

The interplay of sequence conservation and T cell immune recognition

An R-based tool for miRNA data analysis and correlation with clinical ontologies

A taxonomy for bioinformatics tools: exploiting semantics, parallelism, and services for analyzing omics data

Resolving healthcare forum posts via similar thread retrieval

AccuRMSD: a machine learning approach to predicting structure similarity of docked protein complexes

DTC genetic testing and consumer comprehension

Feature subset selection for inferring relative importance of taxonomy

Computational identification of functional network modules associated with the pathogenicity of Fusarium verticillioides

Construction of protein backbone pieces using segment-based FBCCD and Cryo-EM skeleton

Relapsing-remitting multiple scleroris and the role of vitamin D: an agent based model

Evidence of post translational modification bias extracted from the tRNA and corresponding amino acid interplay across a set of diverse organisms

A system for ubiquitous distributed acquisition of voice alteration samples through a mobile application

A novel classification method for predicting acute hypotensive episodes in critical care

Utilizing twilight zone sequence similarities to increase the accuracy of protein 3D structure comparison

The epitope landscape of CRC liver metastases analyzed by whole-exome sequencing and in silico epitope prediction

Promises and challenges in analysis of biological big data

Network-regularized bi-clique finding for tumor stratification

Improving decoy databases for protein folding algorithms

Towards the characterization of normal peripheral immune cells with data from ImmPort

Heuristic parallelizable algorithm for similarity based biosystems comparison

Towards a natural walking monitor for pulmonary patients using simple smart phones

Mining massive SNP data for identifying associated SNPs and uncovering gene relationships

In silico designing and experimental validation of a potential small molecule inhibitor against vibrio cholerae AphB: a LysR-type transcriptional regulator

Biological network clustering by robust NMF

RImmPort: enabling ready-for-analysis immunology research data

Fast dendrogram-based OTU clustering using sequence embedding

Spectral feature selection and its application in high dimensional gene expression studies

Apoptosis centric Bayesian network perturbation analysis of signaling pathways in colorectal cancer for synergistic drug targets discovery

Analysing the distribution of synaptic vesicles using a spatial point process model

SideEffectPTM: an unsupervised topic model to mine adverse drug reactions from health forums

Disease named entity recognition and normalization with DNorm

Scaled sparse high-dimensional tests for localizing sequence variants

Using mobile phones to simulate pulse oximeters: gait analysis predicts oxygen saturation

Identification of protein coding regions in RNA transcripts

Automating risk of bias assessment for clinical trials

A method for reducing the severity of epidemics by allocating vaccines according to centrality

The UniFrac significance test generates different outputs given semantically equivalent inputs

Leveraging hierarchy in medical codes for predictive modeling

Data mining to aid beam angle selection for intensity-modulated radiation therapy

Text mining tools for assisting literature curation

Amb-EM: a SNP-based prediction of HLA alleles using ambiguous HLA data

Approximation algorithms for sorting by signed short reversals

An analysis of conformational changes upon RNA-protein binding

Unconstrained gene tree diameters for deep coalescence

Conditional random fields for morphological analysis of wireless ECG signals

Dose and time relationship through probabilistic graphical models of gene expression time course toxicogenomics data

Integrated miRNA and mRNA analysis of time series microarray data

Modeling climate-dependent population dynamics of mosquitoes to guide public health policies

Validation and implementation of whole-exome sequencing bioinformatics processes for clinical applications

CNVnet: combining sparse learning and biological networks to capture joint effect of copy number variants

Large highly connected clusters in protein-protein interaction networks

Antidote application: an educational system for treatment of common toxin overdose

SimConcept: a hybrid approach for simplifying composite named entities in biomedicine

An improved algorithm for the sorting by reversals and transpositions problem

High-performance recursive dynamic programming for bioinformatics using MM-like flexible kernels

InstantGenotype: a non-parametric model for genotype inference using microarray probe intensities

Dynamic coordinate registration method for image-guided surgery

CLARK, accurate and efficient classification of DNA sequences

Graph-theoretic analysis of epileptic seizures on scalp EEG recordings

A comparison of combined p-value methods for gene differential expression using RNA-seq data

Comparing and optimizing transcriptome assembly pipeline for diploid wheat

Improving identification of key players in aging via network de-noising

One feature doesn't fit all: characterizing topological features of targets in signaling networks

A structured approach to ensemble learning for Alzheimer's disease prediction

FStitch: a fast and simple algorithm for detecting nascent RNA transcripts

Data-driven prediction of cancer cell fates with a nonlinear model of signaling pathways

An author topic analysis on NCI DCP/DCCPS PIs

A Hadoop-Galaxy adapter for user-friendly and scalable data-intensive bioinformatics in Galaxy

A flexible volumetric comparison of protein cavities can reveal patterns in ligand binding specificity

De novo assembly of ultra-deep sequencing data

Joint inference for end-to-end coreference resolution for clinical notes

MotionTalk: personalized home rehabilitation system for assisting patients with impaired mobility

Identifying causal variants at loci with multiple signals of association

IPED2: inheritance path based pedigree reconstruction algorithm for complicated pedigrees

Constructing burrows-wheeler transforms of large string collections via merging

A web-based tool to analyze semantic similarity networks

icuARM-II: improving the reliability of personalized risk prediction in pediatric intensive care units

Quantitative trait loci mapping with microarray marker intensities

Graph methods for protein-nucleotide interactions

Understanding user intents in online health forums

Are we there yet?: feasibility of continuous stress assessment via wireless physiological sensors

Individual haplotyping prediction agreements

Learning parameter sets for alignment advising

Focus: a new multilayer graph model for short read analysis and extraction of biologically relevant features

Detecting privacy-sensitive events in medical text

Prioritization of genomic locus pairs for testing epistasis

Haplotype-centered mapping for improved alignments and genetic association studies

A fast and lightweight filter-based algorithm for circular pattern matching

Pathway analysis with signaling hypergraphs

Strand: fast sequence comparison using mapreduce and locality sensitive hashing

NINJA: boolean modelling and formal verification of tiered-rate chemical reaction networks (extended abstract)

omniClassifier: a desktop grid computing system for big data prediction modeling

Computational analysis of the stability of SCF ligases employing domain information

Discovering dysregulated phenotype-related gene patterns

An automated pipeline for discovering gene expression patterns associated with increased cancer survival time

Deep autoencoder neural networks for gene ontology annotation predictions

A novel semi-supervised learning approach to analyzing metagenomic reads

A noise-aware method for building radiation hybrid maps

GraphSpace: sharing and collaborating through networks on the web

Challenges in adapting text mining for full text articles to assist pathway curation

Genome dynamics in coevolved genomes: database management system for tracing mutations

Community detection-based features for sequence classification

Care coordination metrics of patients sharing among physicians: a social network analytic approach

PseudoLasso: leveraging read alignment in homologous regions to correct pseudogene expression estimates via RNASeq

Inferring ancestry in mouse genomes using a hidden Markov model

A collaborative filtering approach to assess individual condition risk based on patients' social network data

DDI2PPI: an integrated web server for protein-protein interaction and residue contact matrix predictions

A workflow for the computational identification of candidate regulatory elements in noncoding DNA

Multi-channel synapse validation on confocal images of mammalian neurons

Using 2-node hypergraph clustering coefficients to analyze disease-gene networks

Predicting protein contact maps by bagging decision trees

On clinical decision support

An improved algorithm for the sorting by reversals and transpositions problem

Content Provider	ACM Digital Library
Author	Dias, Ulisses Oliveira, Andre Rodrigues Dias, Zanoni
Abstract	Genome comparison among closely related species has revealed that organisms share large blocks of DNA sequence and that the ordering of these blocks may change across species. The main explanation is that genomes undergo large scale mutational events, also called rearrangements, during the evolutionary process. Reversals and transpositions are classic rearrangement operations. While a large body of literature exists on how to efficiently compute the reversal distance between genomes as well as to compute an approximate value for the transposition distance, these works generally do not take into account both reversals and transpositions. This paper presents a polynomial-time algorithm for the problem when both operations are allowed. Previous algorithms have approximation factor of 2, we do not improve this factor for every permutations. However, we show that the only step which does not guarantee an approximation ratio better than 1.75 occurs in rare situations. In addition, we carried out a batch of tests using 49,000 simulated instances and the greatest approximation factor we noticed was 1.8. Overall, we observed that our ratio is lower than 1.25 in more than 90% of the cases. When we consider only permutations whose sizes range from 200 to 500 (maximum size in our dataset), we observe that our ratio is lower than 1.25 in every case. We also show that our algorithm outperforms the state of the art by significant margins.
Starting Page	400
Ending Page	409
Page Count	10
File Format	PDF
ISBN	9781450328944
DOI	10.1145/2649387.2649417
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2014-09-20
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Reversals Transpositions Genome rearrangement
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in