NDLI: De Novo Peptide Sequencing Based on Vertex Contraction Algorithm

Content Provider	IEEE Xplore Digital Library
Author	Zhexue Wei Daming Zhu
Copyright Year	2012
Abstract	De novo peptide sequencing is an important method for peptide sequencing and protein identification. It can be transformed into a special case of paths avoiding forbidden pairs problem (PAFP). General PAFP is NP-complete. The definition of PAFP is the following: Given a directed a cyclic graph $G=(V, E)$, two distinguished vertices source $s$, sink $t \in V$, a set of forbidden pairs $F \subset V \times V $, and an edge weight function $w : E \to R$, asking for a maximum weight path from $s$ to $t$ passing at most one vertex from each forbidden pair. In the process of transformation from de novo peptide sequencing to PAFP, forbidden pairs have nested structure. We give a vertex contraction algorithm which is designed based on nested structure of forbidden pairs to solve paths avoiding forbidden pairs problem. The time complexity of vertex contraction algorithm is $O(\|V\|^3)$.
Starting Page	48
Ending Page	52
File Size	197946
Page Count	5
File Format	PDF
ISBN	9781467313650
DOI	10.1109/CSO.2012.19
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2012-06-23
Publisher Place	China
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Algorithm design and analysis Greedy algorithms forbidden pairs Peptides de novo peptide sequencing Amino acids Educational institutions vertex contraction Complexity theory Dynamic programming nested structure
Content Type	Text
Resource Type	Article

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

Antilope—A Lagrangian Relaxation Approach to the de novo Peptide Sequencing Problem

A multi-edge graph based de novo peptide sequencing method for HCD spectra

NovoPair: De novo peptide sequencing for tandem mass spectra pair

Comparative analysis of Vertex Cover computation algorithms for varied graphs

A Unique Vertex Deleting Algorithm for Graph Isomorphism

Poster: De novo protein identification by dynamic programming

An algorithm for the shortest pairs of arc-disjoint paths problem

Discretization Algorithm Based on Cut Set Knowledge Granularity

A dynamic programming algorithm for finding highest-scoring forbidden-pairs paths with variable vertex scores.

De Novo Peptide Sequencing Based on Vertex Contraction Algorithm

Similar Documents

Antilope—A Lagrangian Relaxation Approach to the de novo Peptide Sequencing Problem

A multi-edge graph based de novo peptide sequencing method for HCD spectra

NovoPair: De novo peptide sequencing for tandem mass spectra pair

Comparative analysis of Vertex Cover computation algorithms for varied graphs

A Unique Vertex Deleting Algorithm for Graph Isomorphism

Poster: De novo protein identification by dynamic programming

An algorithm for the shortest pairs of arc-disjoint paths problem

Discretization Algorithm Based on Cut Set Knowledge Granularity

A dynamic programming algorithm for finding highest-scoring forbidden-pairs paths with variable vertex scores.

De Novo Peptide Sequencing Based on Vertex Contraction Algorithm