OcrV1, PubMed, Corpus, bibRecord, 000056

Approximate strip exchanging.

Identifieur interne : 000056 ( PubMed/Corpus ); précédent : 000055; suivant : 000057

Approximate strip exchanging.

Auteurs : Swapnoneel Roy ; Ashok Kumar Thakur

Source :

International journal of computational biology and drug design [ 1756-0756 ] ; 2008.

RBID : pubmed:20055003

English descriptors

KwdEn :
- Algorithms, Computational Biology, Computer Simulation, Gene Rearrangement, Genome, Models, Genetic.
MESH :
- Algorithms, Computational Biology, Computer Simulation, Gene Rearrangement, Genome, Models, Genetic.

Abstract

Genome rearrangements have been modelled by a variety of primitives such as reversals, transpositions, block moves and block interchanges. We consider such a genome rearrangement primitive Strip Exchanges. Given a permutation, the challenge is to sort it by using minimum number of strip exchanges. A strip exchanging move interchanges the positions of two chosen strips so that they merge with other strips. The strip exchange problem is to sort a permutation using minimum number of strip exchanges. We present here the first non-trivial 2-approximation algorithm to this problem. We also observe that sorting by strip-exchanges is fixed-parameter-tractable. Lastly we discuss the application of strip exchanges in a different area Optical Character Recognition (OCR) with an example.

PubMed: 20055003

Links to Exploration step

pubmed:20055003

Le document en format XML

<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">Approximate strip exchanging.</title>
<author><name sortKey="Roy, Swapnoneel" sort="Roy, Swapnoneel" uniqKey="Roy S" first="Swapnoneel" last="Roy">Swapnoneel Roy</name>
<affiliation><nlm:affiliation>IBM India Pvt. Ltd., India Software Lab, Information Management, c/ Embassy Golf Links Business Park, Bangalore, India. swapnoneel.roy@in.ibm.com</nlm:affiliation>
</affiliation>
</author>
<author><name sortKey="Thakur, Ashok Kumar" sort="Thakur, Ashok Kumar" uniqKey="Thakur A" first="Ashok Kumar" last="Thakur">Ashok Kumar Thakur</name>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">PubMed</idno>
<date when="2008">2008</date>
<idno type="RBID">pubmed:20055003</idno>
<idno type="pmid">20055003</idno>
<idno type="wicri:Area/PubMed/Corpus">000056</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en">Approximate strip exchanging.</title>
<author><name sortKey="Roy, Swapnoneel" sort="Roy, Swapnoneel" uniqKey="Roy S" first="Swapnoneel" last="Roy">Swapnoneel Roy</name>
<affiliation><nlm:affiliation>IBM India Pvt. Ltd., India Software Lab, Information Management, c/ Embassy Golf Links Business Park, Bangalore, India. swapnoneel.roy@in.ibm.com</nlm:affiliation>
</affiliation>
</author>
<author><name sortKey="Thakur, Ashok Kumar" sort="Thakur, Ashok Kumar" uniqKey="Thakur A" first="Ashok Kumar" last="Thakur">Ashok Kumar Thakur</name>
</author>
</analytic>
<series><title level="j">International journal of computational biology and drug design</title>
<idno type="ISSN">1756-0756</idno>
<imprint><date when="2008" type="published">2008</date>
</imprint>
</series>
</biblStruct>
</sourceDesc>
</fileDesc>
<profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Algorithms</term>
<term>Computational Biology</term>
<term>Computer Simulation</term>
<term>Gene Rearrangement</term>
<term>Genome</term>
<term>Models, Genetic</term>
</keywords>
<keywords scheme="MESH" xml:lang="en"><term>Algorithms</term>
<term>Computational Biology</term>
<term>Computer Simulation</term>
<term>Gene Rearrangement</term>
<term>Genome</term>
<term>Models, Genetic</term>
</keywords>
</textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">Genome rearrangements have been modelled by a variety of primitives such as reversals, transpositions, block moves and block interchanges. We consider such a genome rearrangement primitive Strip Exchanges. Given a permutation, the challenge is to sort it by using minimum number of strip exchanges. A strip exchanging move interchanges the positions of two chosen strips so that they merge with other strips. The strip exchange problem is to sort a permutation using minimum number of strip exchanges. We present here the first non-trivial 2-approximation algorithm to this problem. We also observe that sorting by strip-exchanges is fixed-parameter-tractable. Lastly we discuss the application of strip exchanges in a different area Optical Character Recognition (OCR) with an example.</div>
</front>
</TEI>
<pubmed><MedlineCitation Owner="NLM" Status="MEDLINE"><PMID Version="1">20055003</PMID>
<DateCreated><Year>2010</Year>
<Month>01</Month>
<Day>08</Day>
</DateCreated>
<DateCompleted><Year>2010</Year>
<Month>02</Month>
<Day>18</Day>
</DateCompleted>
<Article PubModel="Print"><Journal><ISSN IssnType="Print">1756-0756</ISSN>
<JournalIssue CitedMedium="Print"><Volume>1</Volume>
<Issue>1</Issue>
<PubDate><Year>2008</Year>
</PubDate>
</JournalIssue>
<Title>International journal of computational biology and drug design</Title>
<ISOAbbreviation>Int J Comput Biol Drug Des</ISOAbbreviation>
</Journal>
<ArticleTitle>Approximate strip exchanging.</ArticleTitle>
<Pagination><MedlinePgn>88-101</MedlinePgn>
</Pagination>
<Abstract><AbstractText>Genome rearrangements have been modelled by a variety of primitives such as reversals, transpositions, block moves and block interchanges. We consider such a genome rearrangement primitive Strip Exchanges. Given a permutation, the challenge is to sort it by using minimum number of strip exchanges. A strip exchanging move interchanges the positions of two chosen strips so that they merge with other strips. The strip exchange problem is to sort a permutation using minimum number of strip exchanges. We present here the first non-trivial 2-approximation algorithm to this problem. We also observe that sorting by strip-exchanges is fixed-parameter-tractable. Lastly we discuss the application of strip exchanges in a different area Optical Character Recognition (OCR) with an example.</AbstractText>
</Abstract>
<AuthorList CompleteYN="Y"><Author ValidYN="Y"><LastName>Roy</LastName>
<ForeName>Swapnoneel</ForeName>
<Initials>S</Initials>
<AffiliationInfo><Affiliation>IBM India Pvt. Ltd., India Software Lab, Information Management, c/ Embassy Golf Links Business Park, Bangalore, India. swapnoneel.roy@in.ibm.com</Affiliation>
</AffiliationInfo>
</Author>
<Author ValidYN="Y"><LastName>Thakur</LastName>
<ForeName>Ashok Kumar</ForeName>
<Initials>AK</Initials>
</Author>
</AuthorList>
<Language>eng</Language>
<PublicationTypeList><PublicationType UI="D016428">Journal Article</PublicationType>
</PublicationTypeList>
</Article>
<MedlineJournalInfo><Country>England</Country>
<MedlineTA>Int J Comput Biol Drug Des</MedlineTA>
<NlmUniqueID>101479540</NlmUniqueID>
<ISSNLinking>1756-0756</ISSNLinking>
</MedlineJournalInfo>
<CitationSubset>IM</CitationSubset>
<MeshHeadingList><MeshHeading><DescriptorName MajorTopicYN="Y" UI="D000465">Algorithms</DescriptorName>
</MeshHeading>
<MeshHeading><DescriptorName MajorTopicYN="N" UI="D019295">Computational Biology</DescriptorName>
</MeshHeading>
<MeshHeading><DescriptorName MajorTopicYN="N" UI="D003198">Computer Simulation</DescriptorName>
</MeshHeading>
<MeshHeading><DescriptorName MajorTopicYN="Y" UI="D015321">Gene Rearrangement</DescriptorName>
</MeshHeading>
<MeshHeading><DescriptorName MajorTopicYN="N" UI="D016678">Genome</DescriptorName>
</MeshHeading>
<MeshHeading><DescriptorName MajorTopicYN="Y" UI="D008957">Models, Genetic</DescriptorName>
</MeshHeading>
</MeshHeadingList>
</MedlineCitation>
<PubmedData><History><PubMedPubDate PubStatus="entrez"><Year>2010</Year>
<Month>1</Month>
<Day>9</Day>
<Hour>6</Hour>
<Minute>0</Minute>
</PubMedPubDate>
<PubMedPubDate PubStatus="pubmed"><Year>2008</Year>
<Month>1</Month>
<Day>1</Day>
<Hour>0</Hour>
<Minute>0</Minute>
</PubMedPubDate>
<PubMedPubDate PubStatus="medline"><Year>2010</Year>
<Month>2</Month>
<Day>19</Day>
<Hour>6</Hour>
<Minute>0</Minute>
</PubMedPubDate>
</History>
<PublicationStatus>ppublish</PublicationStatus>
<ArticleIdList><ArticleId IdType="pubmed">20055003</ArticleId>
</ArticleIdList>
</PubmedData>
</pubmed>
</record>

Pour manipuler ce document sous Unix (Dilib)

EXPLOR_STEP=$WICRI_ROOT/Ticri/CIDE/explor/OcrV1/Data/PubMed/Corpus

HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000056 | SxmlIndent | more

HfdSelect -h $EXPLOR_AREA/Data/PubMed/Corpus/biblio.hfd -nk 000056 | SxmlIndent | more

Pour mettre un lien sur cette page dans le réseau Wicri

{{Explor lien
   |wiki=    Ticri/CIDE
   |area=    OcrV1
   |flux=    PubMed
   |étape=   Corpus
   |type=    RBID
   |clé=     pubmed:20055003
   |texte=   Approximate strip exchanging.
}}

Pour générer des pages wiki

HfdIndexSelect -h $EXPLOR_AREA/Data/PubMed/Corpus/RBID.i   -Sk "pubmed:20055003" \
       | HfdSelect -Kh $EXPLOR_AREA/Data/PubMed/Corpus/biblio.hfd   \
       | NlmPubMed2Wicri -a OcrV1

This area was generated with Dilib version V0.6.32.
Data generation: Sat Nov 11 16:53:45 2017. Site generation: Mon Mar 11 23:15:16 2024

	Serveur d'exploration sur l'OCR
	Attention, ce site est en cours de développement ! Attention, site généré par des moyens informatiques à partir de corpus bruts. Les informations ne sont donc pas validées.

Serveur d'exploration sur l'OCR

Approximate strip exchanging.

Approximate strip exchanging.

Source :

English descriptors

Abstract

Links to Exploration step

Le document en format XML

Pour manipuler ce document sous Unix (Dilib)

Pour mettre un lien sur cette page dans le réseau Wicri

Pour générer des pages wiki